Selectionsort: Unterschied zwischen den Versionen
K Flbkwikiadmin verschob die Seite Selection-sort nach Selectionsort |
Keine Bearbeitungszusammenfassung |
||
| Zeile 69: | Zeile 69: | ||
Ein besonderes Merkmal dieses Algorithmus ist, dass seine Laufzeit **unabhängig** von der anfänglichen Sortierung der Elemente ist. Um eine Datenstruktur (z. B. ein [[Array]]) mit <math>n</math> Einträgen zu sortieren, muss <math>n - 1</math> Mal das Minimum durch Vergleichen bestimmt werden. | Ein besonderes Merkmal dieses Algorithmus ist, dass seine Laufzeit **unabhängig** von der anfänglichen Sortierung der Elemente ist. Um eine Datenstruktur (z. B. ein [[Array]]) mit <math>n</math> Einträgen zu sortieren, muss <math>n - 1</math> Mal das Minimum durch Vergleichen bestimmt werden. | ||
Bei der ersten Bestimmung des Minimums sind <math>n - 1</math> Vergleiche notwendig, bei der zweiten <math>n - 2</math> Vergleiche, und so weiter bis zum letzten Durchlauf mit exakt 1 Vergleich. Mit der [[ | Bei der ersten Bestimmung des Minimums sind <math>n - 1</math> Vergleiche notwendig, bei der zweiten <math>n - 2</math> Vergleiche, und so weiter bis zum letzten Durchlauf mit exakt 1 Vergleich. Mit der [[Arithmetische_Reihe|gaußschen Summenformel]] erhält man die Gesamtanzahl der immer notwendigen Vergleiche: | ||
<math>(n - 1) + (n - 2) + \dots + 1 = \frac{n(n - 1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n</math> | <math>(n - 1) + (n - 2) + \dots + 1 = \frac{n(n - 1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n</math> | ||