Sortowanie przez kopcowanie
Układa listę w kopiec, czyli drzewo, w którym każdy rodzic jest większy od swoich dzieci. Potem raz za razem przenosi największą wartość na koniec.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(1)
- nie
- tak
Najlepszy przypadek: jak czas rośnie z rozmiarem listy n, gdy dane są dla tego algorytmu najłatwiejsze.
Średni: jak czas zwykle rośnie z n. Przy n² dwa razy więcej wartości sortuje się około czterech razy dłużej; n log n rośnie dużo wolniej.
Najgorszy przypadek: jak rośnie czas przy najtrudniejszych danych. Ważny, gdy sortowanie nigdy nie może zwolnić.
Pamięć: ile dodatkowej pamięci potrzeba poza listą. 1 to kilka zmiennych, n to kopia listy.
Stabilny: dwie równe wartości zachowują pierwotną kolejność. Ważne przy sortowaniu rekordów według jednego pola.
Bez dodatkowej pamięci: sortuje w samej liście, bez drugiej listy.
- porównywanie
- przenoszenie
- na właściwym miejscu
Spróbuj: Wybierz listę odwróconą. Budowa kopca prawie nie wymaga zamian, a potem każda runda przenosi największą wartość na koniec.
Jak to działa
Kopiec mieści się w samej liście: wartość na pozycji o numerze i ma dzieci na pozycjach 2i+1 oraz 2i+2, a największa wartość jest zawsze na początku. Zamień ją z ostatnią wartością, zmniejsz kopiec o jedno miejsce i napraw go. Posortowana część rośnie od prawej.
Kiedy warto go użyć
Gdy sortowanie ma być szybkie nawet w najgorszym przypadku i nie zajmować dodatkowej pamięci, na przykład na małych urządzeniach. Średnio działa wolniej niż sortowanie szybkie, więc często jest tylko planem awaryjnym.