Porównania
Zamiany
Wyjęte

  • Przesiewanie w dół
  • Porównywane
  • Zamienione
  • Na miejscu

Więcej o sortowaniu przez kopcowanie

Sortowanie przez kopcowanie

Sortowanie przez kopcowanie (heapsort) czyta listę jako drzewo binarne i układa ją w kopiec typu max, w którym każdy rodzic jest co najmniej tak duży jak jego dzieci. Największa wartość jest wtedy na szczycie. Przenieś ją na koniec, gdzie zostaje, napraw kopiec i powtórz. Aplikacja rysuje kopiec jako drzewo nad słupkami, więc możesz śledzić każdą wartość przesiewaną w dół. Naciśnij Odtwórz, aby obejrzeć sortowanie, albo Krok i Wstecz, aby przechodzić po jednym porównaniu. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Drzewo nad słupkami pokazuje te same wartości jako kopiec. Kafelki liczą porównania, zamiany i wartości wyjęte z kopca. Wybierz liczbę słupków, ich początkowy układ albo wpisz własne liczby. Gdy plansza jest zaznaczona, strzałki przechodzą o krok, spacja uruchamia i wstrzymuje, a Home i End przenoszą na początek i na koniec.

Jak to działa

  1. Wybierz liczbę słupków i ich początkowy układ: losowy, prawie posortowany, odwrócony lub z kilkoma różnymi wartościami. Możesz też wpisać własne liczby.
  2. Naciśnij Odtwórz albo używaj przycisków Krok i Wstecz, aby przechodzić po jednym porównaniu. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce sortowania.
  3. Obserwuj drzewo: najpierw każdy rodzic jest przesiewany w dół, aż powstanie kopiec, potem korzeń trafia na koniec, a kopiec zmniejsza się o jeden.

Jak działa sortowanie przez kopcowanie

Czytaj listę jako drzewo: wartość na pozycji i ma dzieci na pozycjach 2i + 1 oraz 2i + 2. Zbuduj kopiec typu max, przesiewając w dół każdego rodzica, zaczynając od ostatniego: dopóki wartość jest mniejsza od większego ze swoich dzieci, zamieniają się miejscami. Gdy w korzeniu jest największa wartość, zamień ją z ostatnią wartością kopca. Ta wartość jest już na stałe na swoim miejscu, kopiec jest o jeden krótszy, a nowy korzeń jest przesiewany w dół, aby znów powstał kopiec. Powtarzaj, aż kopiec będzie pusty.

Zawsze n log n, w miejscu

Drzewo ma około log₂ n poziomów, więc każde przesiewanie w dół wymaga najwyżej około 2 log₂ n porównań, a budowa kopca mniej niż 2n. Daje to w najgorszym przypadku około 2n log₂ n porównań, bez bufora: dla 40 wartości najwyżej 352. W przeciwieństwie do sortowania szybkiego nie ma złych danych wejściowych, a w przeciwieństwie do sortowania przez scalanie nie potrzebuje dodatkowej pamięci. W praktyce zwykle jest wolniejsze od obu, bo skacze po liście, i nie jest stabilne.

Często zadawane pytania

Jak działa sortowanie przez kopcowanie?

Zamienia listę w kopiec typu max, czyli drzewo zapisane w liście, w którym każdy rodzic jest co najmniej tak duży jak jego dzieci. Potem raz za razem przenosi największą wartość z korzenia na koniec kopca i przesiewa nowy korzeń w dół, aby naprawić kopiec.

Czym jest kopiec?

To zupełne drzewo binarne zapisane w liście bez wskaźników: dziećmi pozycji i są pozycje 2i + 1 oraz 2i + 2. W kopcu typu max każdy rodzic jest co najmniej tak duży jak jego dzieci, więc największa wartość jest zawsze w korzeniu, na pozycji 0.

Dlaczego budowa kopca jest szybka?

Większość wartości jest blisko dołu drzewa i może zejść najwyżej o poziom lub dwa. Po zsumowaniu pracy na wszystkich poziomach cała budowa wymaga mniej niż 2n porównań, a nie n log n.

Czy sortowanie przez kopcowanie jest stabilne?

Nie. Przenoszenie korzenia na koniec przesuwa wartości na duże odległości, więc równe wartości mogą zmienić kolejność.

Czy moje liczby są gdzieś wysyłane?

Nie. Sortowanie działa w przeglądarce, a ostatnie ustawienia zostają w jej pamięci lokalnej.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Przejdź do edytora