Lekcja: "Algorytmy sortujące - drzewa binarne, sortowanie przez kopcowanie"
Sortowanie przez kopcowanie (heap sort)
W tej lekcji poznaliście już w jaki sposób tworzyć kopiec i jak dokonać jego rozbioru. Sortowanie przez kopcowanie (sortowanie kopcem) to nic innego jak połączenie tych dwóch elementów. W zbiorze tworzymy kopiec, a następnie dokonujemy jego rozbioru. W wyniku tego zbiór zostanie posortowany.
Sortowanie to jest dość szybkim algorytmemi nie pochlania zbyt wiele zasobów pamięci. Jego asymptotyczna złożoność czasowa to O(n log n).
W praktyce algorytm ten jest nieco wolniejszy od sortowania szybkiego, ale ma lepszą pesymistyczną złożoność czasową - O(n log n), podczas gdy dla quicksort jest to O(n2) co jest nie do przyjęcia dla dużych zbiorów danych.
Sortowanie przez kopcowanie jest niestabilne, co może być czasami uznawane za wadę. Algorytm sortuje w miejscu.
