Veröffentlicht · wird verbessert
Algorithm
Sortieralgorithmen bringen Daten in Reihenfolge: Mergesort, Quicksort, Heapsort, Stabilität, die untere Schranke n log n und eingebaute Sortierfunktionen.
Sortieren bedeutet, Elemente in eine festgelegte Reihenfolge zu bringen, etwa numerisch, alphabetisch oder zeitlich. Man unterscheidet vergleichsbasierte Verfahren (Bubblesort, Insertionsort, Selectionsort, Mergesort, Quicksort, Heapsort), die nur fragen, ob ein Element vor einem anderen steht, und nicht vergleichsbasierte Verfahren wie Countingsort und Radixsort, die ganzzahlige Werte oder deren Ziffern direkt nutzen.
Sortieren ist der Vorbereitungsschritt für binäre Suche, Duplikatentfernung, das Zusammenführen von Intervallen, Ranglisten und vieles mehr. Deshalb gehört es zu den ersten Algorithmen, die man lernt. Wer die untere Schranke Ω(n log n) für Vergleichsverfahren, den Unterschied zwischen stabilen und In-place-Verfahren sowie das Verhalten eingebauter Sortierfunktionen kennt, etwa Timsort in Python oder Introsort in den meisten Implementierungen von C++ std::sort, trifft im Projekt und im Vorstellungsgespräch die richtige Wahl.
Zum Lernen verfolgt man Insertionsort, Mergesort und Quicksort zunächst von Hand an kleinen Arrays, implementiert dann Mergesort und Quicksort selbst und vergleicht besten, mittleren und schlechtesten Fall. Danach übt man das Sortieren mit Schlüsselfunktionen und Vergleichern und löst Aufgaben, die auf Sortieren aufbauen, etwa das Zusammenführen von Intervallen oder das Zählen von Inversionen.
Mergesort halbiert die Eingabe und führt die Hälften zusammen, Quicksort partitioniert um ein Pivotelement. Beide laufen im Mittel in O(n log n).
Ein stabiles Verfahren erhält die ursprüngliche Reihenfolge gleicher Schlüssel, ein In-place-Verfahren braucht kaum zusätzlichen Speicher. Was wichtiger ist, hängt von der Aufgabe ab.
Ein Entscheidungsbaum-Argument zeigt, dass jedes Vergleichsverfahren im schlechtesten Fall größenordnungsmäßig n log n Vergleiche braucht. Mergesort und Heapsort erreichen diese Schranke.
Countingsort und Radixsort sortieren ganze Zahlen mit begrenztem Wertebereich oder begrenzter Stellenzahl in nahezu linearer Zeit, ohne Elemente miteinander zu vergleichen.
merge_sort teilt die Liste in zwei Hälften, sortiert jede rekursiv und führt sie zusammen, indem es immer das kleinere der beiden vorderen Elemente übernimmt. Bei Gleichheit wird das linke Element zuerst genommen (<=), dadurch ist das Verfahren stabil; es läuft für jede Eingabe in O(n log n). Die letzte Zeile vergleicht das Ergebnis mit der eingebauten Funktion sorted().
merge_sort.py
def merge_sort(items):
"""Return a new sorted list (stable, O(n log n))."""
if len(items) <= 1:
return list(items)
mid = len(items) // 2
left, right = merge_sort(items[:mid]), merge_sort(items[mid:])
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # take the left one on ties: stable
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
return merged + left[i:] + right[j:]
if __name__ == "__main__":
data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data)) # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort(data) == sorted(data)) # True
python merge_sort.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Sortieren.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Sortieren aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.