EMZETT.Glossar
1620 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
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 · Insertionsort und Selectionsort · Recursion (Rekursion)
Ganzer Artikel im Wiki →Teile und herrsche (Divide and Conquer) Teile und herrsche zerlegt ein Problem in kleinere gleichartige Teilprobleme, löst sie (oft rekursiv) und setzt die Teillösungen zusammen.
Drei Schritte: teilen, die Teile lösen, zusammenführen. Klassische Beispiele sind Mergesort, Quicksort und die Binäre Suche. Oft ergibt sich daraus eine Laufzeit von O(n log n) statt O(n²).
Verwandt: Big-O-Notation · Binäre Suche · Dynamische Programmierung · Mergesort · Quicksort · Recursion (Rekursion)
Ganzer Artikel im Wiki →