Nicht vergleichende Sortierverfahren und Pythons sort()
Untersuchen Sie Counting Sort und Radix Sort für Integer-Arrays und verstehen Sie, wie Pythons Timsort bei Aufrufen der integrierten Sortierfunktionen intern arbeitet.
Nicht vergleichende Sortierverfahren und Pythons sort() ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Die O(n log n)-Untergrenze für Vergleiche
Jeder Sortieralgorithmus, der die Reihenfolge nur durch Vergleiche von Elementen bestimmt, benötigt im Worst Case mindestens Ω(n log n) Vergleiche. Dies wird durch das Entscheidungsbaumargument bewiesen: Beim Sortieren von n Elementen muss zwischen n! möglichen Anordnungen unterschieden werden. Ein binärer Entscheidungsbaum (jeder Knoten ist ein Vergleich) benötigt mindestens log₂(n!) ≈ n log₂(n) Ebenen. Um diese Schranke zu unterschreiten, benötigen wir zusätzliche Informationen über die Elemente – beispielsweise, dass es sich um beschränkte Ganzzahlen handelt.
import math
for n in [5, 10, 100, 1000]:
lower_bound = n * math.log2(n)
factorial_log = sum(math.log2(i) for i in range(1, n+1))
print(f'n={n}: n*log2(n)={lower_bound:.1f}, log2(n!)={factorial_log:.1f}')
# n log n is a tight bound on comparison-based sortingCounting Sort: Nach Häufigkeit sortieren
Counting Sort funktioniert, indem die Häufigkeit jedes Werts gezählt und anschließend das sortierte Array aus den Zählwerten rekonstruiert wird. Dafür muss der Wertebereich [0, k) im Voraus bekannt sein. Zeitkomplexität: O(n + k); Speicherkomplexität: O(k). Für kleine k im Verhältnis zu n (z. B. beim Sortieren von Altersangaben von 0–120 oder einstelligen Zahlen) ist Counting Sort schneller als alle vergleichsbasierten Sortierverfahren. Bei großem k macht der Speicherbedarf O(k) den Algorithmus unpraktisch.
def counting_sort(arr, k=None):
if not arr: return []
if k is None: k = max(arr) + 1
count = [0] * k
for n in arr:
count[n] += 1
result = []
for val, freq in enumerate(count):
result.extend([val] * freq)
return result
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr)) # [1, 2, 2, 3, 3, 4, 8]
# O(n + k) where k = 9 (max value + 1)Stabile Counting-Sortierung mit kumulativen Zählwerten
Bei einer stabilen Counting-Sortierung (wichtig, wenn Objekte nach einem Schlüssel sortiert werden) berechnen Sie kumulative Zählwerte, sodass cum[v] die Startposition des Werts v in der Ausgabe angibt. Durchlaufen Sie das Eingabearray von rechts nach links, platzieren Sie jedes Element an der Position cum[key] - 1 und verringern Sie diese Position. Dadurch entsteht eine stabile Sortierung – Elemente mit demselben Schlüssel behalten ihre ursprüngliche relative Reihenfolge bei.
def counting_sort_stable(arr, k):
count = [0] * k
for n in arr: count[n] += 1
# Cumulative counts: count[v] = first position for value v
for i in range(1, k): count[i] += count[i-1]
output = [0] * len(arr)
# Fill from right to maintain stability
for n in reversed(arr):
count[n] -= 1
output[count[n]] = n
return output
print(counting_sort_stable([4,2,2,8,3,3,1], 9))
# [1, 2, 2, 3, 3, 4, 8]Radix-Sortierung: Ziffer für Ziffer sortieren
Radix-Sortierung sortiert Ganzzahlen Ziffer für Ziffer – von der Ziffer mit der kleinsten Wertigkeit (LSD) bis zur Ziffer mit der größten Wertigkeit (MSD) –, wobei an jeder Ziffernposition eine stabile Sortierung (z. B. Counting-Sortierung) verwendet wird. Nach d Durchläufen (einem pro Ziffer) ist das Array vollständig sortiert. Zeitkomplexität: O(d × (n + k)), wobei d = Anzahl der Ziffern und k = Basis (in der Regel 10) gilt. Für n Ganzzahlen mit einer oberen Schranke W gilt d = log_k(W), also insgesamt O(n log_k(W)).
def radix_sort(arr):
if not arr: return []
max_val = max(arr)
exp = 1 # current digit position (1, 10, 100, ...)
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for n_ in arr: count[(n_ // exp) % 10] += 1
for i in range(1, 10): count[i] += count[i-1]
for n_ in reversed(arr):
d = (n_ // exp) % 10
count[d] -= 1
output[count[d]] = n_
return output
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]Bucket-Sortierung: Auf Buckets verteilen
Bucket-Sortierung verteilt Elemente anhand ihres Wertebereichs auf eine feste Anzahl von Buckets, sortiert jeden Bucket (bei kleinen Buckets mit Insertion-Sortierung) und fügt die Buckets anschließend zusammen. Bei gleichmäßig verteilten Daten im Bereich [0, 1) erreicht die Sortierung mit n Buckets eine durchschnittliche Laufzeit von O(n). Laufzeit: durchschnittlich O(n + k), im schlechtesten Fall O(n²) (wenn sich alle Elemente in einem Bucket befinden). Besonders nützlich ist sie, wenn die Datenverteilung bekannt und annähernd gleichmäßig ist.
def bucket_sort(arr):
if not arr: return []
n = len(arr)
min_v, max_v = min(arr), max(arr)
if min_v == max_v: return arr[:]
buckets = [[] for _ in range(n)]
# Map each value to a bucket index
for v in arr:
idx = int((v - min_v) / (max_v - min_v + 1e-9) * n)
idx = min(idx, n - 1)
buckets[idx].append(v)
result = []
for bucket in buckets:
bucket.sort() # insertion sort for small buckets
result.extend(bucket)
return result
print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21]))
# sorted listTimsort in Python unter der Haube
Python verwendet für sorted() und list.sort() den von Tim Peters im Jahr 2002 entwickelten Timsort. Timsort ist eine Kombination aus Merge-Sortierung und Insertion-Sortierung. Der Algorithmus sucht nach „natürlichen Läufen“ (bereits sortierten Teilfolgen) und verwendet Insertion-Sortierung, um Läufe mit bis zu 64 Elementen aufzubauen. Anschließend führt er die Läufe mithilfe von Merge-Sortierung zusammen und nutzt dabei mehrere Optimierungen: Galloping (das Überspringen großer Elementblöcke, wenn ein Lauf dominiert) und das Stapeln von Läufen nach ihrer Länge.
# Timsort properties:
# - Stable
# - O(n log n) worst case
# - O(n) best case (data already sorted)
# - O(n) auxiliary space
# - Highly optimised for real-world data with runs
import time
# Nearly sorted data: Timsort is extremely fast
nearly_sorted = list(range(10000))
nearly_sorted[-1] = 0 # one mis-placed element
t = time.perf_counter()
not_used = sorted(nearly_sorted)
elapsed = time.perf_counter() - t
print(f'Timsort on nearly-sorted n=10000: {elapsed*1000:.3f} ms')Pythons sort() im Vergleich zu sorted(): Die wichtigsten Unterschiede
list.sort() sortiert direkt an Ort und Stelle, gibt None zurück und funktioniert nur bei Listen. sorted(iterable) funktioniert mit jedem Iterable (Tupeln, Generatoren, Dictionaries) und gibt eine neue Liste zurück. Beide akzeptieren die Parameter key und reverse. Ein häufiger Fehler besteht darin, den Rückgabewert von lst.sort() einer Variablen zuzuweisen und sich dann zu wundern, warum er None ist. Verwenden Sie immer sorted(), wenn Sie die sortierte Version benötigen und das Original beibehalten möchten.
nums = [3, 1, 4, 1, 5, 9]
# in-place: returns None
result = nums.sort()
print(result) # None (common bug!)
print(nums) # [1, 1, 3, 4, 5, 9] (modified)
nums2 = [3, 1, 4, 1, 5, 9]
# out-of-place: returns new list
result2 = sorted(nums2)
print(result2) # [1, 1, 3, 4, 5, 9]
print(nums2) # [3, 1, 4, 1, 5, 9] (unchanged)Benutzerdefinierte Sortierschlüssel in Interviews
Die Sortierung in Python akzeptiert eine key-Funktion, die einmal pro Element ausgewertet wird (anders als der in C für jedes Paar aufgerufene Comparator). Häufige Sortierschlüssel in Interviews sind len für die Länge von Zeichenketten, lambda x: -x für absteigende Sortierung, lambda x: (x[1], x[0]) für Sortierung nach mehreren Schlüsseln und str.lower für Sortierung ohne Berücksichtigung der Groß-/Kleinschreibung. Pythons Sortierung ist garantiert stabil, daher funktionieren Sortierungen nach mehreren Schlüsseln korrekt.
# Sort by length, then alphabetically
words = ['banana', 'fig', 'apple', 'date', 'kiwi']
print(sorted(words, key=lambda w: (len(w), w)))
# ['fig', 'date', 'kiwi', 'apple', 'banana']
# Sort integers as strings (largest concatenation first)
nums = [3, 30, 34, 5, 9]
print(sorted(map(str, nums), key=lambda a: a*10, reverse=True))
# ['9', '5', '34', '3', '30'] => '9534330'
# Descending sort
print(sorted([3,1,4,1,5], reverse=True)) # [5,4,3,1,1]Welche Sortierung Sie in Interviews verwenden sollten
Wählen Sie die passende Sortierung für den jeweiligen Kontext:
- Verwenden Sie Python-Sortierungen mit sorted()/list.sort(): Dies ist die Standardwahl für alle Interviewaufgaben – Timsort ist optimal
- Counting-Sortierung: wenn die Werte kleine, nach oben beschränkte Ganzzahlen sind (0 bis k, k klein)
- Radix-Sortierung: wenn viele Ganzzahlen mit bekannter Bitbreite oder Ziffernanzahl sortiert werden sollen
- Bucket-Sortierung: wenn es sich um gleichmäßig verteilte Gleitkommazahlen in einem bekannten Bereich handelt
- Implementieren Sie Merge-Sortierung: wenn Sie aufgefordert werden, eine stabile Sortierung mit O(n log n) von Grund auf zu programmieren
# Problem: sort array of 0s, 1s, 2s efficiently
# Counting sort: O(n), O(1) space (k=3 is tiny)
def sort_012(arr):
count = [0, 0, 0]
for n in arr:
count[n] += 1
i = 0
for val in range(3):
for _ in range(count[val]):
arr[i] = val; i += 1
arr = [2, 0, 2, 1, 1, 0]
sort_012(arr)
print(arr) # [0, 0, 1, 1, 2, 2]Ohne Sortierung sortieren: Top-k mit einem Heap
Bei vielen Interviewaufgaben werden Ergebnisse verlangt, die einer Sortierung ähneln, ohne dass eine vollständige Sortierung erforderlich ist. Um die k größten Elemente zu finden, läuft ein Min-Heap der Größe k in O(n log k) – schneller als O(n log n), wenn k << n ist. Um das k-größte Element zu finden, benötigt Quickselect durchschnittlich O(n). Um den Median zu finden, benötigt der Ansatz mit zwei Heaps O(log n) pro Einfügevorgang. Diese Ansätze für eine teilweise Sortierung sollten Sie als schnellere Alternativen zur vollständigen Sortierung kennen.
import heapq
# Top-k with heap: O(n log k)
def top_k(nums, k):
return heapq.nlargest(k, nums) # uses heap of size k internally
print(top_k([3,2,1,5,6,4], 2)) # [6, 5]
# kth largest: quickselect O(n) average
import random
def kth_largest(nums, k):
def _select(lo, hi, target):
if lo >= hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]; i = lo - 1
for j in range(lo, hi):
if nums[j] >= pivot: i+=1; nums[i],nums[j]=nums[j],nums[i]
nums[i+1],nums[hi]=nums[hi],nums[i+1]
p = i + 1
if p == target: return nums[p]
return _select(lo, p-1, target) if target < p else _select(p+1, hi, target)
return _select(0, len(nums)-1, k-1)
print(kth_largest([3,2,1,5,6,4], 2)) # 5Sortierstabilität bei Sortierungen nach mehreren Schlüsseln
Stabilität ermöglicht eine korrekte Sortierung nach mehreren Schlüsseln: Sortieren Sie zuerst stabil nach dem sekundären Schlüssel und anschließend stabil nach dem primären Schlüssel. Bei gleichen Werten des primären Schlüssels bleibt die Reihenfolge nach dem sekundären Schlüssel erhalten. Diese Technik wird in Datenbanken (ORDER BY col1, col2) und bei Radix-Sortierung verwendet (jeder Durchlauf für eine Ziffer muss stabil sein, damit der Gesamtalgorithmus korrekt funktioniert). Pythons Sortierung ist immer stabil, daher funktioniert dieses Muster zuverlässig.
data = [
('Alice', 'Math', 90),
('Bob', 'Science', 85),
('Carol', 'Math', 90),
('Dave', 'Science', 90),
]
# Sort by score DESC, then by subject ASC (for ties)
# Step 1: sort by subject (secondary)
data.sort(key=lambda x: x[1])
# Step 2: sort by score DESC (primary, stable)
data.sort(key=lambda x: x[2], reverse=True)
for row in data:
print(row)
# All score=90 rows: Math before Science (preserved from step 1)Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Lektionszusammenfassung
In dieser Lektion haben Sie Folgendes gelernt: Vergleichssortierungen sind nach unten durch O(n log n) beschränkt – um diese Schranke zu unterschreiten, sind Informationen außerhalb von Vergleichen erforderlich, etwa beschränkte Ganzzahlen, Counting-Sortierung erreicht O(n + k), indem sie Häufigkeiten zählt, Radix-Sortierung verarbeitet Ziffern mit insgesamt O(d × (n + k)), und Bucket-Sortierung nutzt eine gleichmäßige Verteilung für durchschnittlich O(n), und Pythons Timsort ist die praktische Standardwahl – stabil, im schlechtesten Fall O(n log n), im besten Fall O(n) und bei realen Daten schneller als jede handgeschriebene Alternative. Als Nächstes lernen Sie die klassische binäre Suche gründlich kennen.
Häufig gestellte Fragen
Ist die Lektion „Nicht vergleichende Sortierverfahren und Pythons sort()“ kostenlos?
Ja — der vollständige Text von „Nicht vergleichende Sortierverfahren und Pythons sort()“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Nicht vergleichende Sortierverfahren und Pythons sort()“?
Untersuchen Sie Counting Sort und Radix Sort für Integer-Arrays und verstehen Sie, wie Pythons Timsort bei Aufrufen der integrierten Sortierfunktionen intern arbeitet. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Nicht vergleichende Sortierverfahren und Pythons sort()“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Bubble Sort und Insertion Sort
- Merge Sort: Teilen, sortieren, zusammenführen
- Quick Sort und Pivot-Auswahl
- Nicht vergleichende Sortierverfahren und Pythons sort()