HeapSort, a MergeSort i QuickSort :-) - od strony "chytrości" ;-)

Jeśli porównuję te 3 algorytmy, to największe wrażenie na mnie zawsze robi heap sort, po naszemu sorotwanie przez kopcowanie.
Czemu? Bo jest najbardziej "chytrym" algorytmem ;-)

Taki merge sort jest niemal intuicyjny, podziel to co chcesz sortować na 2 równe/podobne części, posortuj każdą z nich merge sortem, a to co wróci połącz tak, że z każdego z posortowanych podciągów wybieraj mniejszy element z wierzchu....
Quick sort jest niby trochę bardziej chytry, ale chytrość jest głównie w metodzie partition i w tym jak się zapewnia, że wszystkie mniejsze bądź równe od elementu rozdzielającego są przed nim, a wszystkie większe za nim... tutaj jednak chytrość widać dopiero w użyciu metody parition do wyznaczania mediany i ogólnie dowolnej n-tej liczby/wartości w ciągu.

Ale heap sort jest najbardziej chytry.
Najpierw sama idea kopca, nie jest taka oczywista. Na pierwszy rzut oka nie widać jednak, że samo utrzymanie tego, że rodzic jest zawsze większy lub równy swoim dzieciom wystarczy do wstępnego uporządkowania.... że można to zrobić liniowo i że wystarczy przyjąć, że dziećmi są węzły o indeksach 2*i i 2*i+1....
Już na to musiało być trudno wpaść.... 
Ale później wpaść na to, żeby najpierw zbudować kopiec... a później skorzystać z tego, że największy element jest na jego szczycie, podmienić go z ostatnim elementem w kopcu, zmniejszyć rozmiar kopca i przywrócić własność kopca dla pierwszego elementu..... i tak dalej..... to jest genialne :-)
Chyba nawet użycie tego do zbudowania kolejki priorytetowej nie jest aż tak odkrywcze ;-)

Chociaż z drugiej strony, pamiętam że zrozumienie metody partition z Quick Sorta zajęło mi z 30 minut tępego patrzenia się na pseudokod ;-) a z heap sortem poszło szybciej ;-)
Merge sort jakoś od razu załapałem, ale zawsze miałem problemy z implementacją, bo zawsze mi się gdzieś indeksy myliły ;-) w merge'u.
Tu heap sort był zawsze najmilszy, jakoś tak najłatwiej się go zawsze implementowało ;-)

[a to wszystko wyżej przez to, że mi laptop dziś przez dość dłuższą chwilę chorował i czytałem Cormena i spółkę - Wstęp do algorytmów ;-)]


Podobne posty^beta
Przeżycie artystyczne ;-)
Jak czytać kod...
Koszmarne Garbage Collectory part 2 ;)
Dalsze zabawy z ePubGeneratorem :-)
Książki które zmieniły moje życie