EMZETT.Glossar
736 Begriffe aus IT, Netzwerk, Sicherheit und Programmierung: erst kurz erklärt, dann ausführlicher. Suche nach einem Wort oder wähle einen Buchstaben.
2 Treffer
Quicksort Quicksort ist ein schnelles Sortierverfahren nach dem Prinzip „Teile und herrsche“: Es wählt ein Pivot-Element, teilt die Liste in kleinere und größere Werte und sortiert beide Teile rekursiv.
Im Durchschnitt braucht Quicksort O(n log n) Schritte und sortiert meist direkt im vorhandenen Speicher. Im schlechtesten Fall (ungünstige Pivot-Wahl bei bereits sortierten Daten) sind es O(n²). Eine zufällige oder mittlere Pivot-Wahl vermeidet das in der Praxis.
Verwandt: Bubblesort · Mergesort · Big-O-Notation · Recursion (Rekursion) · Sorting (Sortieren)
Ganzer Artikel im Wiki →Mergesort Mergesort teilt die Liste in zwei Hälften, sortiert beide rekursiv und mischt (engl. merge) die sortierten Hälften zu einer sortierten Liste. Es arbeitet in jedem Fall in O(n log n) und ist stabil.
Anders als Quicksort hat Mergesort keinen schlechten Sonderfall; dafür braucht es zusätzlichen Speicher von O(n). Es eignet sich gut für verkettete Listen und für das Sortieren von Daten, die nicht in den Arbeitsspeicher passen (externes Sortieren).
Verwandt: Bubblesort · Quicksort · Binäre Suche · Dynamische Programmierung · Recursion (Rekursion) · Sorting (Sortieren)
Ganzer Artikel im Wiki →