Suchen, Sortieren und Effizienz

Eine Suche klärt, ob ein Suchwert vorkommt und wo er vorkommt. Eine Liste hat nummerierte Positionen, die Indizes heißen. Python zählt ab null: In [7, 3, 9, 3, 5] steht an Index 0 die 7 und an Index 4 die 5. Der Wert und sein Index beantworten verschiedene Fragen.

Ein Element nach dem anderen prüfen

Die lineare Suche, auch sequenzielle Suche genannt, beginnt beim ersten Element und vergleicht jedes Element mit dem Suchwert. Sie gibt sofort einen Index zurück, wenn sie einen Treffer findet. Endet die Liste ohne Treffer, gibt sie -1 zurück, unser Zeichen für „nicht gefunden“.

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

len(items) liefert die Anzahl der Elemente. range(len(items)) liefert jeden zulässigen Index, beginnend bei 0 und endend unmittelbar vor der Länge. items[i] liest den Wert am aktuellen Index. Ein return beendet die Funktion, sodass ein späterer Treffer den ersten nie ersetzt.

Die Suche nach 3 in der obigen Liste verläuft so:

1. Vergleiche an Index 0 die 7 mit der 3. Sie sind verschieden, also suche weiter.
2. Vergleiche an Index 1 die 3 mit der 3. Sie stimmen überein, also gib Index 1 zurück.

Das Ergebnis ist nach zwei Vergleichen Index 1. Die zweite 3 an Index 3 wird nicht mehr geprüft. Bei der Suche nach 4 werden stattdessen 7, 3, 9, 3 und 5 geprüft; nach fünf Vergleichen wird -1 zurückgegeben. Ein zurückgegebener Index 1 bezeichnet das zweite Element, nicht ein Element mit dem Wert 1.

Den Aufwand zählen

Sei $n$ die Anzahl der Elemente. Bei einer nicht leeren Liste ist der beste Fall ein Vergleich: Das erste Element stimmt überein. Der schlechteste Fall sind $n$ Vergleiche: Der Suchwert steht am Ende oder fehlt. Eine leere Liste benötigt null Vergleiche und gibt -1 zurück.

Kommt ein Suchwert einmal vor und steht er mit gleicher Wahrscheinlichkeit an jeder Position, beträgt die durchschnittliche Anzahl der Vergleiche

Bei 1.000 Elementen sind das 500,5 Vergleiche. Ein Durchschnitt kann eine Bruchzahl sein, obwohl jede einzelne Suche eine ganze Anzahl von Vergleichen ausführt. Dieser Durchschnitt beschreibt genau diese Verteilung erfolgreicher Suchen; häufige erfolglose Suchen würden den Gesamtdurchschnitt erhöhen.

Den Misserfolg nach der Schleife zurückgeben

Ein else: return -1 innerhalb der Schleife würde beim ersten nicht übereinstimmenden Element aufgeben. Bei [7, 3, 9] würde es die Suche nach 3 zurückweisen, nachdem nur 7 geprüft wurde. Die Rückgabe bei Misserfolg gehört hinter die Schleife, wenn jede Position ausgeschlossen wurde.

Die lineare Suche benötigt weder eine sortierte Reihenfolge noch eine Vorbereitung. Sie funktioniert mit Zahlen, Wörtern oder Datensätzen, die anhand einer ID verglichen werden. Eine für sortierte Daten entwickelte Version kann anhalten, wenn sie die mögliche Position des Suchwerts passiert: In [2, 5, 8, 12] reicht es, die 8 zu sehen, um die 6 auszuschließen. Der obige Code sucht bewusst weiter, bis er einen Treffer findet oder das Ende erreicht.

Verwandte Aufgaben nutzen denselben Durchlauf, aber eine andere Abbruchregel. Um jedes Vorkommen zu zählen, jeden passenden Index zu sammeln oder ein größtes Element zu finden, muss die gesamte Liste geprüft werden; bei der Suche nach dem ersten Treffer ist eine frühere Rückgabe möglich.

Die binäre Suche nutzt die sortierte Reihenfolge, um Positionen auszuschließen, ohne sie einzeln zu prüfen. Ihre Eingabe muss aufsteigend sortiert sein. Außerdem benötigt sie schnellen Zugriff auf ein Element an einem gewählten Index, wie ihn ein Array oder eine Python-Liste bietet.

Ein Intervall mit eingeschlossenen Endpunkten verwalten

low und high markieren die erste und letzte noch mögliche Position; beide Endpunkte gehören dazu. Beginne mit low = 0 und high = len(items) - 1. Wähle den mittleren Index durch Abrunden. Ist der mittlere Wert zu klein, ist jeder Wert links davon ebenfalls zu klein; verschiebe low hinter die Mitte. Ist er zu groß, verschiebe high unmittelbar vor die Mitte.

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

// dividiert und rundet ab. Die Schleife schließt den Fall low == high ein, weil noch eine ungeprüfte Position übrig ist. Bei low > high ist das Suchintervall leer.

Treffer und Misserfolg nachvollziehen

Verwende [3, 8, 12, 17, 23, 31, 42, 56, 64, 77, 85] mit den Indizes 0 bis 10. Bei der Suche nach 64 ist der erste mittlere Index 5 und enthält 31. Da 31 zu klein ist, setze low = 6. Der nächste mittlere Index ist 8 und enthält 64. Gib nach zwei Prüfungen eines mittleren Elements 8 zurück.

Bei der Suche nach 20 in derselben Liste:

Jetzt ist das Suchintervall leer, gib also -1 zurück. Dieser Misserfolg ist begründet: Die sortierte Reihenfolge rechtfertigte jeden ausgeschlossenen Teil.

Warum das Verfahren schnell ist

Jede erfolglose Prüfung lässt höchstens die Hälfte des Suchintervalls übrig. Bei einer nicht leeren Liste beträgt die maximale Anzahl der Prüfungen mittlerer Elemente $\lfloor {\log }_{2}n\rfloor +1$. Der Logarithmus zur Basis 2 beschreibt wiederholtes Halbieren: $2^{10}=1.024$, sodass tausend Elemente höchstens 10 Prüfungen benötigen; eine Million benötigt höchstens 20. Eine Prüfung in diesem Python-Code kann zwei Vergleiche ausführen, == und <. Prüfungen und Vergleiche sind verschiedene Zähleinheiten.

Voraussetzungen und Fehler an den Rändern

Die sortierte Reihenfolge ist unerlässlich. Die Suche nach 2 in [9, 2, 7, 4, 1] sieht zuerst 7 und verwirft den rechten Teil, sieht dann 9 und verwirft den verbliebenen Treffer an Index 1. Auch der schnelle Zugriff auf die Mitte ist wichtig: Musst du Verweisen folgen, um die Mitte einer verketteten Liste zu erreichen, geht der Geschwindigkeitsvorteil der Array-Version verloren.

Schließe das geprüfte mittlere Element nach einem Misserfolg immer aus. Mit low = mid kann [10, 20] bei der Suche nach 20 für immer unverändert bleiben. while low < high überspringt den letzten Kandidaten und schlägt bei der Suche nach 5 in [5] fehl. Bei einer leeren Liste gilt high = -1, sodass die korrekte Schleife nie beginnt.

Bei Duplikaten gibt diese Version einen beliebigen passenden Index zurück. Die Suche nach 4 in [2, 4, 4, 4, 9] gibt sofort Index 2 zurück; um das erste Vorkommen zu finden, braucht man eine abgewandelte Suche, die nach einem Treffer links weitersucht.

Beim Sortieren werden Elemente nach einem gewählten Schlüssel umgeordnet. Bei aufsteigend sortierten Zahlen ist jedes Element kleiner als oder gleich dem nächsten. „Nicht absteigend“ lässt gleiche Nachbarn zu: [2, 5, 5, 9] ist sortiert. Die absteigende Reihenfolge kehrt die Richtung um.

Zwei Bedingungen prüfen

Eine korrekte Sortierung muss eine geordnete Ausgabe erzeugen, die genau die ursprünglichen Elemente mit allen Wiederholungen enthält. Das Sortieren von [3, 1, 2] zu [1, 2, 3] gelingt. Sowohl [1, 2] als auch [1, 1, 3] sind falsch, obwohl ihre Nachbarn geordnet sind. Im ersten Fall fehlt ein Element; im zweiten hat sich geändert, welche Elemente vorkommen. Eine Umordnung, die alle Vorkommen erhält, heißt Permutation.

Bei einem Datensatz ist der Schlüssel nur das Feld, anhand dessen verglichen wird. Städte könnten nach Name oder Einwohnerzahl sortiert werden. Wird der Schlüssel mit der Einwohnerzahl verschoben, bewegt sich der gesamte Stadtdatensatz mit; den Namen davon zu trennen würde die Daten verfälschen.

Die Textreihenfolge hängt vom Schlüssel ab

Ein einfacher Textvergleich folgt den Zeichencodes, Zeichen für Zeichen. In ASCII und Unicode nutzen A–Z die Codes 65–90 und a–z die Codes 97–122. Deshalb steht „Zebra“ bei einem einfachen Vergleich vor „apfel“. Der Vergleich kleingeschriebener Kopien kann bei diesen Beispielen eine Reihenfolge unabhängig von Groß- und Kleinschreibung liefern.

Auch Ziffern in Texten verhalten sich wie Zeichen. „10“ steht beim Sortieren vor „9“, weil sein erstes Zeichen „1“ ist. Ein numerischer Schlüssel wandelt diese Zeichenketten in die Zahlen um, die sie darstellen, sodass 9 vor 10 steht. Entscheide, was die Daten bedeuten, bevor du den Vergleich wählst.

Werte verschieben, ohne sie zu verlieren

Eine Vertauschung tauscht zwei Positionen aus. Eine temporäre Variable sichert den Wert, der sonst überschrieben würde:

temp = items[i]
items[i] = items[j]
items[j] = temp

Python erlaubt auch items[i], items[j] = items[j], items[i]. Schreibst du die beiden Zuweisungen, ohne den ersten Wert zu sichern, wird aus [4, 7] die Liste [7, 7]. Bubblesort und Selectionsort verschieben Elemente durch Vertauschungen; Mergesort kopiert Elemente in eine verschmolzene Ausgabe.

Stabilität und Speicher

Ein stabiles Sortierverfahren erhält die ursprüngliche Reihenfolge von Datensätzen mit gleichen Schlüsseln. Beginne mit Ana 85, Ben 92, Cara 85 in alphabetischer Reihenfolge. Eine stabile Sortierung nach absteigender Punktzahl ergibt Ben 92, Ana 85, Cara 85. Ana bleibt vor Cara. So kann eine spätere Sortierung nach Punktzahl innerhalb jeder Punktzahlgruppe eine frühere alphabetische Reihenfolge erhalten. Pythons eingebaute Sortierfunktion ist stabil.

Ein Sortierverfahren, das innerhalb der Liste arbeitet, ordnet die bestehende Liste mit nur wenigen zusätzlichen Variablen um, unabhängig von ihrer Länge. Die hier behandelten Verfahren Bubblesort und Selectionsort arbeiten innerhalb der Liste. Das übliche Mergesort benötigt zusätzlichen Speicher proportional zur Anzahl der Elemente. Stabilität und Speicher beschreiben verschiedene Eigenschaften: Ein Sortierverfahren kann innerhalb der Liste arbeiten und dennoch instabil sein.

Unordnung mit Inversionen messen

Eine Inversion ist ein Positionspaar, bei dem der Schlüssel eines früheren Elements größer ist als der eines späteren. In [5, 1, 4, 2, 8] sind die Inversionen (5, 1), (5, 4), (5, 2) und (4, 2): insgesamt vier. Die Paare müssen keine Nachbarn sein.

Eine sortierte Liste hat null Inversionen. Eine umgekehrt sortierte Liste aus $n$ verschiedenen Elementen hat $n(n-1)\mathrm{/}2$, also die größtmögliche Anzahl. Gleiche Schlüssel bilden nie eine Inversion: [3, 3, 1] hat zwei, eine für jede 3 vor der 1. Das Zählen von Inversionen hilft, die Anzahl der Vertauschungen bei Bubblesort zu erklären.

Bubblesort vergleicht benachbarte Elemente von links nach rechts. Ist das linke Element größer, vertauscht es das Paar. Jeder Gang durch die Liste ist ein Durchlauf. Ein großes Element kann während eines Durchlaufs wiederholt nach rechts wandern, bis das größte verbliebene Element seine endgültige Position erreicht.

Den ersten Durchlauf verfolgen

Beginne mit [5, 1, 4, 2, 8]:

1. Vergleiche 5 und 1; vertausche sie zu [1, 5, 4, 2, 8].
2. Vergleiche 5 und 4; vertausche sie zu [1, 4, 5, 2, 8].
3. Vergleiche 5 und 2; vertausche sie zu [1, 4, 2, 5, 8].
4. Vergleiche 5 und 8; lass sie unverändert.

Der Durchlauf führt vier Vergleiche und drei Vertauschungen aus. Das größte Element, 8, steht fest. Der Rest ist noch unsortiert: 4 steht vor 2. Ein Durchlauf garantiert die endgültige Position des Maximums, nicht die Reihenfolge aller Elemente.

Durchlauf 2 benötigt nur die ersten vier Positionen. Vergleiche 1 mit 4, vertausche dann 4 mit 2 und vergleiche anschließend 4 mit 5. Das ergibt nach drei weiteren Vergleichen und einer Vertauschung [1, 2, 4, 5, 8]. Durchlauf 3 vergleicht 1 mit 2 und 2 mit 4. Er nimmt keine Vertauschung vor und bestätigt damit, dass die Liste sortiert ist. Insgesamt: neun Vergleiche und vier Vertauschungen.

Jeden Durchlauf verkürzen und vorzeitig abbrechen

def bubble_sort(items):
    n = len(items)
    for p in range(n - 1):
        swapped = False
        for j in range(n - 1 - p):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if not swapped:
            break

Die Durchlaufzählvariable p beginnt bei null. Der größte Wert von j ist n - 2 - p, sodass j + 1 innerhalb des unsortierten Teils bleibt. Setze swapped zu Beginn jedes Durchlaufs zurück; eine Vertauschung in einem früheren Durchlauf sagt nichts darüber aus, ob der aktuelle Durchlauf ein Element bewegt hat.

Nach jedem Durchlauf steht eine weitere Position rechts endgültig fest. Ein Durchlauf ohne Vertauschungen beweist, dass alle verglichenen Nachbarn geordnet sind. Auch das bereits feststehende Suffix ist geordnet, sodass der Algorithmus anhalten kann. Der bestätigende Durchlauf zählt dennoch zum Aufwand.

Besten und schlechtesten Fall vergleichen

Bei einer sortierten, nicht leeren Liste führt die Version mit vorzeitigem Abbruch $n-1$ Vergleiche und null Vertauschungen aus. Bei einer umgekehrt sortierten Liste verschiedener Elemente führt sie

Vergleiche und ebenso viele Vertauschungen aus. Fünf Elemente benötigen 10; 1.000 Elemente benötigen 499.500. Ohne vorzeitigen Abbruch würde das durchgerechnete Beispiel mit fünf Elementen auch den letzten Durchlauf mit einem Vergleich ausführen und auf 10 Vergleiche kommen.

Jede Vertauschung beseitigt genau eine Inversion. Die vier Inversionen der ursprünglichen Beispielliste erklären ihre vier Vertauschungen. Gleiche Nachbarn bleiben an ihrem Platz, weil die Prüfung > verwendet. Dadurch ist diese Version stabil und arbeitet innerhalb der Liste. Ersetzt du > durch >=, kann sich die Reihenfolge von Datensätzen mit gleichen Schlüsseln umkehren.

Die Position ist auch bei wenigen Inversionen wichtig. [5, 1, 2, 3, 4] benötigt vier Vertauschungen und einen zweiten Durchlauf zur Bestätigung der Reihenfolge, also sieben Vergleiche. [2, 3, 4, 5, 1] benötigt ebenfalls vier Vertauschungen, aber seine 1 kann pro Durchlauf nur einmal nach links wandern. Es benötigt alle vier Durchläufe und 10 Vergleiche.

Selectionsort baut links ein sortiertes Präfix auf. Jeder Durchlauf findet das kleinste Element im verbliebenen Suffix und tauscht es dann an die nächste Position des Präfixes. Die Suche findet die Position; die Vertauschung erfolgt nach der Suche.

Einen Index merken

Beginne an Position i mit smallest = i. Vergleiche jedes spätere Element mit items[smallest]. Aktualisiere smallest nur, wenn ein kleineres Element auftaucht. Tausche nach dem Ende der Suche items[i] und items[smallest] aus.

def selection_sort(items):
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        if smallest != i:
            items[i], items[smallest] = items[smallest], items[i]

Würdest du dir nur den kleinsten Wert merken, fehlte dir seine Position für den Austausch. Ein Suchbeginn bei Index 0 würde bereits platzierte Elemente erneut besuchen; die Suche im verbliebenen Teil beginnt unmittelbar nach i.

Die Durchläufe nachvollziehen

Beginne mit [29, 10, 14, 37, 13].

Das dritte Minimum steht bereits an seiner Position, sodass keine Werte bewegt werden. Nach vier Durchläufen muss das letzte Element das größte sein; es benötigt keinen eigenen Durchlauf. Es gibt 10 Vergleiche und drei Vertauschungen, die Elemente bewegen. Die Bedingung im Code überspringt den Austausch einer Position mit sich selbst; ohne diese Bedingung bleibt das Ergebnis unverändert.

Vergleiche und Vertauschungen haben unterschiedliche Kosten

Selectionsort führt immer $n(n-1)\mathrm{/}2$ Elementvergleiche aus: Jeder Durchlauf muss das gesamte verbliebene Suffix prüfen, um dessen Minimum zu bestimmen. Insgesamt sind es 10 bei fünf Elementen oder 499.500 bei 1.000, selbst bei bereits sortierter Eingabe. Eine Suche, die den gemerkten Index nicht ändert, bestimmt das Minimum dieses Durchlaufs, garantiert aber nicht allgemein, dass das verbliebene Suffix geordnet ist.

Bei einer nicht leeren Liste gibt es pro Durchlauf höchstens eine Vertauschung, die Elemente bewegt, also insgesamt höchstens $n-1$. Eine leere Eingabe benötigt keine Durchläufe oder Vertauschungen. Bubblesort kann bei einer umgekehrt sortierten Liste verschiedener Elemente $n(n-1)\mathrm{/}2$ Vertauschungen benötigen. Kostet das Verschieben großer Datensätze viel mehr als der Vergleich ihrer Schlüssel, kann die geringe Anzahl von Vertauschungen bei Selectionsort trotz der vielen Vergleiche wichtig sein. Wer bei jedem neuen Minimum während der Suche vertauscht, verliert diesen Vorteil.

Gleiche Schlüssel können ihre Reihenfolge ändern

Dieses Verfahren mit Vertauschungen arbeitet innerhalb der Liste, ist aber instabil. Bezeichne Datensätze mit gleichen Schlüsseln als 4a und 4b, damit ihre Identität sichtbar ist. Ausgehend von [4a, 4b, 1] tauscht der erste Durchlauf 4a und 1 aus und erzeugt [1, 4b, 4a]. Die gleichen Schlüssel haben ihre ursprüngliche Reihenfolge umgekehrt, obwohl der Algorithmus sie nie direkt als ungleich verglichen hat. Auch wenn während einer Suche das erste gefundene Minimum beibehalten wird, kann eine Vertauschung über größere Distanz einen Datensatz mit gleichem Schlüssel überholen.

Das Verschmelzen führt zwei bereits sortierte Listen zu einer sortierten Ausgabe zusammen. Setze einen Laufindex auf das erste noch nicht verwendete Element jeder Eingabe. Vergleiche diese beiden Kopfelemente, kopiere das kleinere und bewege nur dessen Laufindex weiter.

Das nächste kleinste Element wählen

Verschmelze [3, 27, 38, 43] mit [9, 10, 82]:

Die linke Liste ist nun aufgebraucht. Kopiere die verbliebene 82 ohne weiteren Elementvergleich. Das Ergebnis ist [3, 9, 10, 27, 38, 43, 82] und benötigt sechs Vergleiche. Das Kopieren der Restliste gehört zum Algorithmus: Wer aufhört, sobald die Vergleiche enden, verliert Daten.

Warum kann das Verfahren Elemente hinter den Kopfelementen ignorieren? Jedes Kopfelement ist das kleinste verbliebene Element seiner Liste. Das kleinere Kopfelement ist daher insgesamt das kleinste verbliebene Element. Diese Überlegung gilt auch nach jeder Bewegung eines Laufindex, weil die nicht verwendeten Teile sortiert bleiben.

Den Code zum Verschmelzen lesen

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

append fügt ein Element hinzu. Ein Ausschnitt wie left[i:] enthält die nicht verwendete Restliste und extend kopiert deren Elemente. Wenn die Schleife endet, kann höchstens eine nicht verwendete Restliste nicht leer sein. Ist eine Eingabe zu Beginn leer, führt die Schleife null Vergleiche aus und die andere Liste wird vollständig kopiert.

Vergleiche und Speicher zählen

Für zwei nicht leere Listen der Längen $m$ und $k$ sind höchstens $m+k-1$ Vergleiche der Kopfelemente nötig. Jeder Vergleich platziert ein Element und mindestens das letzte Element kann ohne Vergleich kopiert werden. Die kleinstmögliche Anzahl von Vergleichen beim Verschmelzen entspricht der Länge der kürzeren Liste: Das Verschmelzen von [1, 2, 3] mit [4, 5, 6] benötigt drei Vergleiche, bevor die linke Seite aufgebraucht ist.

Der gesamte Kopieraufwand wächst mit $m+k$, selbst wenn die Vergleiche früh enden, weil jedes Element in der Ausgabe erscheinen muss. Die neue Liste benötigt außerdem Platz für $m+k$ Elemente. Vergleichsanzahl, Kopieraufwand und zusätzlicher Speicher messen verschiedene Teile desselben Vorgangs.

Gleiche Schlüssel und Eingabereihenfolge behandeln

Die Prüfung <= nimmt bei gleichen Schlüsseln das Element von links. Stammen die beiden Eingaben aus aufeinanderfolgenden Teilen einer ursprünglichen Liste, bleibt dadurch der frühere Datensatz vor dem späteren mit gleichem Schlüssel. Diese Regel für gleiche Schlüssel ist für stabiles Mergesort nötig.

Die Voraussetzung sortierter Eingaben ist unverzichtbar. Das Verschmelzen von [5, 1] mit [3] kopiert 3 und dann die Restliste [5, 1] und erzeugt [3, 5, 1]. Die Regel für Kopfelemente schlug fehl, weil 5 nicht der kleinste verbliebene Wert seiner Eingabe war.

Mergesort löst eine große Sortieraufgabe, indem es sie in kleinere Sortieraufgaben zerlegt. Das ist das Prinzip Teile und herrsche: Teile die Liste, sortiere jede Hälfte und verschmelze die sortierten Hälften.

Das Teilen beim Basisfall beenden

Eine Funktion ist rekursiv, wenn sie sich selbst aufruft. Mergesort ruft sich selbst für kürzere Listen auf. Sein Basisfall gibt eine Liste mit null oder einem Element unverändert zurück, da eine solche Liste bereits sortiert ist.

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)

Die Ausschnitte teilen die Eingabe, ohne Elemente zu verlieren. Bei einer ungeraden Länge hat die rechte Seite ein Element mehr: [6, 2, 9, 4, 1, 7, 3] wird in [6, 2, 9] und [4, 1, 7, 3] geteilt. Beide Hälften sind kürzer, sodass die rekursiven Aufrufe schließlich den Basisfall erreichen. Ein Basisfall allein würde die Terminierung nicht sicherstellen, wenn ein Aufruf sich selbst immer wieder die ursprüngliche Liste übergäbe.

Die sortierte Liste wieder zusammensetzen

Vollziehe [38, 27, 43, 3, 9, 82, 10, 15] nach. Die Liste wird in zwei Hälften mit je vier Elementen geteilt, dann in vier Teile mit je zwei Elementen und schließlich in einzelne Elemente. Das Teilen ordnet die Werte nicht um. Die Ordnung entsteht beim Verschmelzen:

1. Verschmelze einzelne Elemente zu [27, 38], [3, 43], [9, 82] und [10, 15]. Jedes Verschmelzen benötigt einen Vergleich: insgesamt vier.
2. Verschmelze die Paare zu [3, 27, 38, 43] und [9, 10, 15, 82]. Jedes Verschmelzen benötigt drei Vergleiche: insgesamt sechs.
3. Verschmelze diese Hälften zu [3, 9, 10, 15, 27, 38, 43, 82]. Das benötigt sieben Vergleiche.

Die vollständige Sortierung benötigt $4+6+7=17$ Elementvergleiche. Zähle nicht nur das abschließende Verschmelzen: Die sortierten Hälften mussten zuerst erzeugt werden. Das obige Beispiel mit sieben Elementen wird nach dieser Teilungsregel mit 14 Vergleichen zu [1, 2, 3, 4, 6, 7, 9] sortiert.

Ebenen und Aufwand pro Ebene zählen

Bei acht Elementen entstehen nach drei Ebenen des Halbierens einzelne Elemente, denn $2^3=8$. Allgemein gibt es etwa ${\log }_{2}n$ Verschmelzungsebenen. Auf einer vollständigen Ebene bearbeiten die Verschmelzungsvorgänge zusammen alle $n$ Elemente. Jede Ebene leistet daher einen zu $n$ proportionalen Aufwand, was zu einem Wachstum wie $n{\log }_{2}n$ führt.

Bei acht Elementen ist $n{\log }_{2}n=24$ eine nützliche, grobe Schranke für die Vergleiche, nicht die genaue Anzahl. Die durchgerechnete Liste benötigte 17; eine bereits sortierte oder umgekehrt sortierte Liste mit acht Elementen benötigt 12. Die Eingabereihenfolge beeinflusst, wann beim Verschmelzen eine Seite aufgebraucht ist, aber jede Liste durchläuft weiterhin die Ebenen des Teilens und Verschmelzens. Bei dieser Version wächst die Anzahl der Vergleiche im besten wie im schlechtesten Fall weiterhin wie $n\log n$.

Bei einer Million Elementen ergeben etwa 20 Ebenen als grobe obere Schätzung etwa 20 Millionen Vergleiche. Selectionsort benötigt etwa 500 Milliarden. Der Unterschied wächst mit der Eingabegröße schnell.

Den zusätzlichen Speicher für die Ausgabe einplanen

Das übliche listenbasierte Mergesort benötigt zusätzlichen Speicher proportional zu $n$. Die Wahl des linken Kopfelements bei gleichen Schlüsseln macht es stabil.

Eine gemessene Laufzeit hängt vom Rechner und vom Programm ab. Eine Schrittzahl beschreibt den Aufwand des Algorithmus anhand einer gewählten wiederholten Operation. Die Eingabegröße, geschrieben $n$, ist die Anzahl der bearbeiteten Elemente.

Die Operation vor dem Zählen wählen

Beim Suchen und Sortieren sind Vergleiche zwischen Elementwerten meist eine sinnvolle Elementaroperation. Zähle Vertauschungen getrennt, wenn das Verschieben von Daten wichtig ist. Bei der binären Suche ist es zweckmäßig, Prüfungen eines mittleren Elements zu zählen. In der Python-Version prüft eine erfolglose Prüfung des mittleren Elements sowohl auf Gleichheit als auch darauf, ob es kleiner ist, und kann daher zwei Elementvergleiche umfassen.

Diese Zahlen beschreiben wiederholte Operationen, keine Codezeilen. Eine Zeile innerhalb einer Schleife kann eine Million Mal ausgeführt werden; mehrere vorbereitende Zeilen werden möglicherweise jeweils einmal ausgeführt.

Fälle bei gleicher Größe unterscheiden

Der beste Fall benötigt unter den zulässigen Eingaben der Größe $n$ die wenigsten Schritte. Der schlechteste Fall benötigt die meisten und bietet eine Garantie. Der durchschnittliche Fall bildet den Durchschnitt über eine angegebene Verteilung von Eingaben.

Bei einer nicht leeren Liste benötigt die lineare Suche einen Vergleich, wenn der Suchwert am Anfang steht, und $n$, wenn er am Ende steht oder fehlt. Der Durchschnitt für erfolgreiche Suchen beträgt $(n+1)\mathrm{/}2$, wenn die erste Trefferposition mit gleicher Wahrscheinlichkeit jede Position sein kann. Der Begriff „Durchschnitt“ setzt diese Verteilung voraus; er bezeichnet nicht bei jedem Algorithmus die Mitte zwischen der besten und der schlechtesten Schrittzahl.

Schleifen in Schrittzahlen übersetzen

Ein Vergleich pro Element bei einem vollständigen Durchlauf ergibt $n$ Vergleiche. Zwei vollständig verschachtelte Schleifen, die jeweils $n$ Mal laufen, führen ihren gemeinsamen Rumpf $n^2$ Mal aus. Ein anderes Muster verschachtelter Schleifen vergleicht jedes Paar nur einmal:

for i in range(n):
    for j in range(i + 1, n):
        compare(items[i], items[j])

Die erste Wiederholung der äußeren Schleife vergleicht ihr Element mit $n-1$ späteren Elementen. Die nächste vergleicht mit $n-2$ und die letzte mit keinem. Insgesamt ergibt sich

Schreibe die Summe vorwärts und rückwärts auf. Jedes untereinanderstehende Paar ergibt zusammen $n$ und es gibt $n-1$ solche Paare. Ihre Summe ist $n(n-1)$, also das Doppelte der ursprünglichen Summe. Für fünf Elemente gilt $4+3+2+1=10$; für 1.000 beträgt die Anzahl der Paare 499.500.

Wiederholtes Halbieren erkennen

Eine Schleife, die ihre verbleibende Arbeit halbiert, benötigt etwa ${\log }_{2}n$ Wiederholungen. Eine Million fällt nach 20 Halbierungen erstmals auf 1 oder weniger: $2^{19}=524.288$ und $2^{20}=\mathrm{1.048.576}$ liegen unter beziehungsweise über einer Million. Das unterscheidet sich stark davon, jedes Mal nur ein Element zu entfernen.

Behalte für Wachstumsvergleiche den am schnellsten wachsenden Term. Die Anzahl der Paare ist $n^2\mathrm{/}2-n\mathrm{/}2$. Bei $n=1.000$ betragen ihre Terme 500.000 und 500, sodass der quadratische Term das Wachstum bestimmt. Das Weglassen des kleineren Terms und des konstanten Faktors beschreibt die Wachstumsfamilie; es macht aus der genauen Anzahl von 499.500 keine genaue Anzahl von einer Million.

Eine Wachstumsrate beschreibt, wie sich der Aufwand bei größerer Eingabe verändert. Sie hilft, Algorithmen über die konkrete Größe eines einzelnen Ablaufs hinaus zu vergleichen.

Die üblichen Familien lesen

Bei exponentiellem Wachstum verdoppelt bereits ein zusätzliches Element die Anzahl: $2^{n+1}=2\times 2^n$. Eine Verdopplung der Eingabe ist eine viel größere Änderung als das Hinzufügen eines Elements.

Größen anhand von Zahlen vergleichen

Für Eingaben mit 10, 100, 1.000 und einer Million Elementen beträgt ${\log }_{2}n$ etwa 3,3, 6,6, 10 und 20. Die entsprechenden Werte von $n{\log }_{2}n$ betragen etwa 33, 664, 9.966 und 20 Millionen. Die quadratischen Werte sind 100, 10.000, eine Million und eine Billion.

Logarithmisches Wachstum ist nicht „die halbe Liste“. Bei einer Million Elementen benötigt wiederholtes Halbieren nur etwa 20 Stufen. Steigt die Eingabe von 1.000 auf 2.000, steigt $n{\log }_{2}n$ von etwa 9.966 auf 21.932, also um den Faktor etwa 2,2. Auch der Logarithmus ändert sich, sodass die Anzahl etwas schneller als linear wächst.

Exponentieller Aufwand wird schnell groß. $2^{10}=1.024$ und $2^{20}$ ist etwa eine Million. Bei einer Milliarde Schritten pro Sekunde dauern $2^{50}$ Schritte immer noch etwa 13 Tage. Ein weiteres Element verdoppelt diese Zeit.

Informelle O-Schreibweisen verwenden

Programmierer bezeichnen diese Familien üblicherweise mit $O(1)$, $O(\log n)$, $O(n)$, $O(n\log n)$, $O(n^2)$ und $O(2^n)$. Hier bezeichnen sie die übliche Wachstumsfamilie im schlechtesten Fall. Lies $O(n^2)$ als „in der Größenordnung n Quadrat“. Die Schreibweise lässt konstante Faktoren und Terme niedrigerer Ordnung weg: $n(n-1)\mathrm{/}2$ Vergleiche gehören zur quadratischen Familie.

Eine O-Schreibweise ist weder eine genaue Laufzeit noch eine Anzahl von Sekunden. Sie behauptet auch nicht, dass jede Eingabe die Schrittzahl des schlechtesten Falls benötigt. Bubblesort mit vorzeitigem Abbruch hat einen linearen besten, aber einen quadratischen schlechtesten Fall.

Den Schnittpunkt finden

Angenommen, Verfahren A benötigt $100n$ Schritte und Verfahren B benötigt $n^2$. Bei 50 Elementen benötigt A 5.000 Schritte und B 2.500. Bei 100 benötigen beide 10.000. Bei 1.000 benötigt A 100.000 und B eine Million. Das langsamere Wachstum von A überwiegt schließlich seinen größeren konstanten Faktor.

Die Hardwaregeschwindigkeit verändert die absoluten Werte, ohne die Wachstumsfamilie zu ändern. Ein 100-mal schnellerer Computer erlaubt einem quadratischen Verfahren, in derselben Zeit nur 10-mal so viele Elemente zu bearbeiten, denn $(10n{)}^2=100n^2$. Ein lineares Verfahren könnte 100-mal so viele bearbeiten. Bei einer kleinen Aufgabe können Vorbereitung und Konstanten dominieren; bei großen Eingaben wird das Wachstum entscheidend.

Eine bekannte Laufzeit und ein Wachstumsmuster ermöglichen eine Prognose für eine größere Aufgabe. Die Prognose ist eine Schätzung, weil die tatsächliche Zeit auch von Implementierung, Speicher, Hardware und anderen Aufgaben des Rechners abhängt.

Erst die Eingabe, dann die Zeit skalieren

Multipliziere bei linearem Aufwand die Zeit mit dem Verhältnis der Eingabegrößen. Dauert eine Suche über eine Million Elemente im schlechtesten Fall 3 Millisekunden, benötigen zehn Millionen Elemente unter vergleichbaren Bedingungen etwa 30 Millisekunden.

Quadriere bei quadratischem Aufwand das Verhältnis. Angenommen, Selectionsort benötigt 2 Sekunden für 50.000 Elemente. Die Verdopplung auf 100.000 Elemente ergibt

Sekunden. Eine Erhöhung auf 500.000 Elemente multipliziert die Eingabegröße mit 10, sodass die Zeitschätzung $2\times {10}^2=200$ Sekunden beträgt. Würdest du die Zeit mit 10 multiplizieren, würdest du den Algorithmus fälschlich als linear behandeln.

Verwende bei Wachstum der Größenordnung $n{\log }_{2}n$ das Verhältnis der beiden vollständigen Ausdrücke. Die Verdopplung einer großen Eingabe kostet etwas mehr als das Doppelte, weil der Logarithmus zusammen mit der Elementzahl steigt.

Von einem Zeitbudget rückwärts rechnen

Nutze dieselbe quadratische Referenzlaufzeit: 2 Sekunden für 50.000 Elemente. Ein Budget von 32 Sekunden erlaubt das 16-Fache der Zeit. Die Eingabe kann um die Quadratwurzel aus 16 wachsen, also um den Faktor 4. Das ergibt etwa 200.000 Elemente. Prüfe die Richtung durch Einsetzen: Die vierfache Eingabe sagt die 16-fache Zeit voraus, also einen Anstieg von 2 auf 32 Sekunden.

Algorithmen bei großer Eingabe vergleichen

Bei einer Million Elementen führt Selectionsort 499.999.500.000 Vergleiche aus, etwa 500 Milliarden. Mergesort benötigt höchstens etwa 20 Millionen. Bei einer angenommenen Milliarde Vergleichen pro Sekunde entsprechen diese Zahlen etwa 500 Sekunden gegenüber 0,02 Sekunden, einem Unterschied um etwa den Faktor 25.000. Diese Rechnung nimmt gleiche Kosten pro Vergleich an, um die Wirkung des Algorithmus für sich zu betrachten; gemessene Programme benötigen auch Zeit für Verschiebungen und Speicherzugriffe.

Eine Wachstumsprognose prüfen

Miss dasselbe Programm bei mehreren Größen, die sich jeweils verdoppeln, etwa 10.000, 20.000 und 40.000 Elementen. Dividiere jede Zeit durch die vorherige. Verhältnisse nahe 2 deuten auf lineares Wachstum hin; etwas über 2 deutet auf $n\log n$ hin; nahe 4 deutet auf quadratisches Wachstum hin.

Halte Rechner und Messmethode gleich. Wiederhole die Durchläufe und verwende ausreichend große Eingaben, damit die Startzeit nicht dominiert. Vergleiche gleichartige Fälle: Eine Suche an der ersten Position bei einer Größe und eine erfolglose Suche bei einer anderen würden Eingabeeffekte mit dem Wachstum vermischen. Bei Bubblesort brauchen sortierte und umgekehrt sortierte Listen unterschiedliche Fallbezeichnungen.

Ergeben sich bei den sich verdoppelnden Größen 0,04, 0,16 und 0,64 Sekunden, sind beide Verhältnisse 4. Das stützt in diesem Bereich ein quadratisches Modell. Ein einzelnes schwankendes Verhältnis ist ein schwächerer Beleg als ein wiederkehrendes Muster. Schrittzahlen für einen bestimmten Ablauf können exakt sein; eine Prognose in Sekunden sollte „etwa“ enthalten und anhand von Messungen geprüft werden.

Ein korrekter Algorithmus hält bei jeder zulässigen Eingabe an und erzeugt die geforderte Ausgabe. Eine Spezifikation nennt die Eingabebedingung und das zugesicherte Ergebnis. Bei der binären Suche ist die Vorbedingung die aufsteigend sortierte Reihenfolge. Die Nachbedingung ist ein passender Index oder genau dann -1, wenn der Suchwert fehlt.

Schritte durch eine Invariante verbinden

Eine Schleifeninvariante ist eine Aussage, die vor Beginn der Schleife gilt und bei jeder Wiederholung erhalten bleibt. Ein Korrektheitsargument prüft, ob sie zu Beginn gilt, erhalten bleibt und was sie beim Ende der Schleife aussagt. Ein separates Terminierungsargument zeigt, dass die Schleife schließlich endet.

Verwende für Selectionsort diese Invariante: Vor Durchlauf i enthalten die ersten i Positionen die i kleinsten Elemente in Reihenfolge.

1. Beginn: Vor Durchlauf 0 ist das Präfix leer. Es erfüllt die Aussage bereits.
2. Erhaltung: Der Durchlauf findet das kleinste verbliebene Element. Es als Nächstes zu platzieren erweitert das sortierte Präfix um eins; das Element ist mindestens so groß wie jedes zuvor platzierte Element.
3. Ende: Nach höchstens $n-1$ Durchläufen bleibt nur das größte Element außerhalb des Präfixes. Die ganze Liste ist sortiert.

Jede Bewegung ist eine Vertauschung, sodass auch die Multimenge der Elemente unverändert bleibt. Eine geordnete Ausgabe allein würde die vollständige Sortierspezifikation nicht erfüllen.

Bubblesort nutzt eine Suffixinvariante: Nach $k$ Durchläufen enthalten die letzten $k$ Positionen die $k$ größten Elemente in Reihenfolge. Der nächste Durchlauf bringt das größte unsortierte Element zu diesem Suffix. Ein Durchlauf ohne Vertauschungen stellt die Ordnung im gesamten verbliebenen Teil fest und erlaubt einen vorzeitigen Abbruch.

Ausgeschlossene Bereiche bei der binären Suche erklären

Verwende die Invariante: Kommt der Suchwert vor, liegt mindestens ein Vorkommen im Bereich von low bis high, einschließlich der Endpunkte. Anfangs umfasst dieser Bereich die ganze Liste. Ist der mittlere Wert zu klein, sind wegen der sortierten Reihenfolge alle Werte an mid und links davon zu klein. Das Setzen von low auf mid + 1 erhält jeden möglichen Treffer. Für die Aktualisierung auf high = mid - 1 gilt dieselbe Überlegung bei zu großen Werten.

Bei einem Treffer erfüllt die zurückgegebene Position unmittelbar die Nachbedingung. Wird das Suchintervall leer, schließt die Invariante einen Suchwert an jeder Stelle der Liste aus. Die Eingabe bleibt sortiert, weil die Suche sie nie verändert.

Zeigen, warum die Ausführung anhält

Eine abnehmende nicht negative ganzzahlige Größe beweist den Fortschritt zu einem Ende. Bei der binären Suche nimmt die Anzahl der infrage kommenden Positionen nach jedem Misserfolg strikt ab. Der geprüfte mittlere Index wird ausgeschlossen, sodass die Schleife nicht endlos denselben Bereich behalten kann. Bubblesort und Selectionsort führen bei nicht leerer Eingabe höchstens $n-1$ Durchläufe und bei leerer Eingabe keine Durchläufe aus.

Mergesort erreicht Listen mit null oder einem Element, weil jeder rekursive Aufruf eine kürzere Liste verwendet. Diese Basisfälle sind sortiert. Unter der Annahme, dass die kürzeren Aufrufe korrekt sortierte Hälften zurückgeben, nimmt das Verschmelzen wiederholt das kleinste verbliebene Element und erhält alle Elemente. So wird die Korrektheit bis zum ursprünglichen Aufruf zurückgetragen.

Tests für eine andere Aufgabe nutzen

Ein Test vergleicht ein tatsächliches mit einem erwarteten Ergebnis. Viele bestandene ausgewählte Tests stärken das Vertrauen, während eine einzige fehlschlagende zulässige Eingabe ein Gegenbeispiel ist, das die Korrektheit widerlegt. Ein allgemeines Invariantenargument deckt die unbegrenzte Familie möglicher Eingaben ab, die eine endliche Sammlung von Beispieltests ungeprüft lässt. Tests sind besonders nützlich, um zu prüfen, ob tatsächlicher Code das im Argument verwendete Verfahren implementiert.

Ein Randfall ist eine zulässige Eingabe nahe einem Rand, an dem Annahmen und Schleifengrenzen leicht falsch gewählt werden. Leite das erwartete Ergebnis vor der Ausführung des Codes aus der Spezifikation ab. Sonst kann eine fehlerhafte Programmausgabe unbemerkt zu deiner erwarteten Antwort werden.

Listen wählen, die Ränder prüfen

Teste leere Listen und Listen mit einem oder zwei Elementen; bereits sortierte und umgekehrt sortierte Listen; wiederholte und lauter gleiche Werte; negative Zahlen sowie ungerade und gerade Längen. Beziehe bei Suchen die erste und letzte Position sowie fehlende Suchwerte unterhalb, oberhalb und zwischen gespeicherten Werten ein.

Eine binäre Suche in einer leeren Liste sollte -1 zurückgeben, ohne auf ein Element zuzugreifen: low = 0 und high = -1 machen das anfängliche Suchintervall leer. Das Sortieren von [3, 3, 3] sollte drei Vorkommen von 3 zurückgeben. Eine Ausgabe von [3] wäre geordnet, würde aber die Elemente nicht erhalten.

Den kleinsten Fehlerfall nachvollziehen

Eine binäre Suche mit while low < high tritt bei [5] mit dem Suchwert 5 nicht in ihre Schleife ein. Die Korrektur lautet low <= high, da ein Intervall mit einer Position noch einen Kandidaten enthält. Dieser Test mit einem Element zeigt den Rand deutlicher als eine lange Liste.

Mit low = mid setzt die Suche nach 20 in [10, 20] den mittleren Index auf 0, sieht 10 und belässt low bei 0. Bei der nächsten Wiederholung ist das Suchintervall unverändert. Verwende low = mid + 1, um eine bereits geprüfte Position auszuschließen. Eine Liste mit zwei Elementen und dem Suchwert am Ende deckt diese Endlosschleife auf.

Bubblesort vergleicht items[j] mit items[j + 1]. Im ersten Durchlauf ist der letzte zulässige linke Index n - 2. Ein Fortsetzen bis n - 1 liest über die Liste hinaus und löst Pythons IndexError aus. Ein solcher Fehler um eine Position an einem Rand heißt Off-by-one-Fehler.

Beide Zusicherungen für die Ausgabe prüfen

Prüfe bei einer Sortierung die Reihenfolge benachbarter Elemente und die Anzahl jedes ursprünglichen Elements. Verwende gekennzeichnete Datensätze, um die Stabilität zu testen. Bei Ana 85, Ben 92, Cara 85 muss Ana vor Cara bleiben, wenn eine stabile Sortierung nach Punktzahl gleiche Punktzahlen gruppiert. Eine Prüfung nur der Punktzahlen würde eine Vertauschung dieser beiden Datensätze übersehen.

Erzeuge auch zufällige Listen. Vergleiche ihre Ergebnisse mit einer vertrauenswürdigen Implementierung wie Pythons sorted. Behalte Duplikate und verschiedene Längen in den erzeugten Eingaben bei. Schlägt ein Test fehl, verkleinere die Eingabe so, dass der Fehler erhalten bleibt, und vollziehe sie dann von Hand nach. Behalte das kleine Beispiel als Regressionstest, damit der behobene Fehler weiterhin erkennbar bleibt.

Den mittleren Index sicher berechnen

Pythons ganze Zahlen wachsen bei Bedarf, sodass (low + high) // 2 nicht überläuft. Manche Sprachen verwenden ganze Zahlen mit fester Bitbreite. Bei sehr großen nicht negativen Indizes kann ihre Summe den darstellbaren Bereich überschreiten. In Java springt das Ergebnis bei einem Ganzzahlüberlauf zurück; der Überlauf einer vorzeichenbehafteten ganzen Zahl in C ist undefiniertes Verhalten.

Berechne bei zulässigen Indizes und low <= high stattdessen low + (high - low) // 2. Die Differenz ist nicht negativ und das Ergebnis bleibt zwischen den Endpunkten. So wird derselbe abgerundete mittlere Index berechnet, ohne die möglicherweise überlaufende Summe zu bilden. Randwerttests und Überlegungen zur Zahlendarstellung der Sprache wirken hier zusammen.

Ein Algorithmus passt zu einer Aufgabe, wenn seine Anforderungen und Kosten zu den Daten und der auszuführenden Arbeit passen. Berücksichtige die Eingabereihenfolge, den Zugriff auf Positionen, die Anzahl künftiger Operationen, zusätzlichen Speicher, Stabilität und die Kosten für das Verschieben von Datensätzen.

Die Verfahren vergleichen

Die binäre Suche benötigt außerdem eine sortierte Reihenfolge und schnellen Zugriff auf die Mitte. Ein guter Vergleich bezieht diese Voraussetzungen ein; eine geringe Anzahl von Prüfungen allein lässt die Kosten für die Vorbereitung ungeeigneter Daten außer Acht.

Entscheiden, ob sich vorheriges Sortieren lohnt

Für eine Suche in einer Million unsortierter Elemente kostet die lineare Suche höchstens eine Million Vergleiche. Vorheriges Sortieren mit Mergesort kostet etwa 20 Millionen Vergleiche vor der ersten binären Suche, die dann höchstens 20 Prüfungen der Mitte benötigt. Die Vorbereitung übersteigt die Ersparnis bei dieser einen Suche bei Weitem.

Bei 100 Suchen in einer unveränderten Liste können wiederholte lineare Suchen 100 Millionen Vergleiche kosten. Einmaliges Sortieren und 100 binäre Suchen kosten etwa 20 Millionen Vergleiche plus 2.000 Prüfungen der Mitte. Die Vorbereitung wird wiederverwendet, wodurch der zweite Plan attraktiv wird. Unter diesem groben Kostenmodell liegt der Punkt, ab dem sich das Sortieren lohnt, bei etwa 20 Suchen. Die Schätzung hängt von vergleichbaren Operationskosten und vollständigen Durchläufen im schlechtesten Fall ab; sie ist kein allgemein gültiger Schwellenwert.

Reihenfolge, Verschiebung und Speicher abwägen

Bubblesort kann schnell fertig sein, wenn nur ein benachbartes Paar falsch steht. [1, 2, 4, 3, 5] benötigt eine Vertauschung im ersten Durchlauf und einen zweiten Durchlauf zur Bestätigung der Reihenfolge: sieben Vergleiche. „Nahezu sortiert“ garantiert aber nicht wenige Durchläufe. Ein kleiner Wert ganz rechts kann pro Durchlauf nur eine Position nach links wandern.

Die wenigen Vertauschungen von Selectionsort helfen, wenn Datensätze aufwendig zu verschieben sind. Selectionsort und Bubblesort benötigen beide nur eine feste Menge zusätzlichen Speichers. Mergesort verarbeitet große Listen mit viel langsamer wachsender Laufzeit, aber seine übliche listenbasierte Form benötigt Platz für etwa eine weitere Liste von Elementen.

Müssen Datensätze mit gleichen Schlüsseln ihre frühere Reihenfolge behalten, wähle ein stabiles Verfahren. Eine bereits nach Namen alphabetisch sortierte Liste kann stabil nach Note sortiert werden und innerhalb jeder Notengruppe alphabetisch bleiben. Das gewöhnliche Selectionsort kann diese Reihenfolge gleicher Schlüssel verändern.

Getestete Bibliotheksfunktionen nutzen

Echte Programme nutzen gewöhnlich die eingebaute Sortierfunktion der Sprache. Pythons stabile Sortierung verwendet ein adaptives Verfahren auf Grundlage des Verschmelzens, das üblicherweise Timsort heißt und von bereits vorhandener Ordnung in der Eingabe profitiert. sorted(items) gibt eine neue Liste zurück, während items.sort() die bestehende Liste verändert. Eine Funktion, die als Verhalten ihrer Programmierschnittstelle eine Liste selbst verändert, kann intern dennoch temporären Arbeitsspeicher verwenden; sie muss die oben für die einfachen Sortierverfahren verwendete Definition eines festen zusätzlichen Speicherbedarfs nicht erfüllen.

Bei einer Handvoll Elementen kann einfacher, klarer Code wichtiger sein als das Wachstum. Vergleiche bei großen Sammlungen das Verhalten im schlechtesten Fall und den Speicherbedarf zusammen mit den Eigenschaften, die die Aufgabe tatsächlich verlangt.