Porównania
Zamiany
Podziały

  • Dzielona część
  • Pivot
  • Porównywane
  • Zamienione
  • Na miejscu

Więcej o sortowaniu szybkim

Sortowanie szybkie

Sortowanie szybkie wybiera pivot (element osiowy), przenosi każdą mniejszą wartość przed niego, a każdą inną za niego, a potem tak samo sortuje obie strony. Po każdym podziale pivot jest na swoim ostatecznym miejscu. Zdecyduj, jak wybierany jest pivot, odtwórz sortowanie z dowolną prędkością albo przechodź je po jednym porównaniu i zobacz, dlaczego zły pivot na posortowanej liście spowalnia sortowanie szybkie. 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. Kafelki liczą porównania, zamiany i podziały. Wybierz liczbę słupków, ich początkowy układ albo wpisz własne liczby, a także sposób wyboru pivota. 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. Wybierz regułę pivota: ostatnia wartość, środkowa wartość, losowa wartość lub mediana z trzech. Wypróbuj każdą na posortowanej liście.

Jak działa sortowanie szybkie

Wybierz jedną wartość z sortowanej części jako pivot i przenieś ją na koniec. Przejdź przez pozostałe wartości od lewej do prawej; każda wartość mniejsza od pivota trafia przez zamianę do lewej części, która rośnie od początku. Potem zamień pivot tak, by stanął tuż za lewą częścią. Wszystko przed nim jest teraz mniejsze, a nic za nim nie jest, więc pivot jest na swoim ostatecznym miejscu. Posortuj tak samo część przed nim i część za nim, aż każda część będzie pojedynczą wartością.

Dlaczego pivot ma znaczenie

Gdy pivot wypada blisko środka, każdy podział zmniejsza problem o połowę, a liczba porównań rośnie jak n log n: dla 40 losowych wartości około 190. Gdy pivot jest najmniejszą lub największą wartością, jedna strona jest pusta, a druga zawiera całą resztę. Gdy pivotem jest ostatnia wartość, dzieje się tak w każdym kroku na posortowanej lub odwróconej liście, a sortowanie wymaga n(n − 1)/2 porównań, 780 dla 40 wartości. Losowy pivot lub mediana pierwszej, środkowej i ostatniej wartości w praktyce temu zapobiega.

Często zadawane pytania

Jak działa sortowanie szybkie?

Wybiera pivot, dzieli listę tak, by mniejsze wartości znalazły się przed pivotem, a reszta za nim, a potem sortuje obie strony sortowaniem szybkim. Po każdym podziale pivot jest na swoim ostatecznym miejscu.

Dlaczego sortowanie szybkie jest wolne na posortowanej liście?

Gdy pivotem jest pierwsza lub ostatnia wartość, posortowana lista zawsze daje jako pivot najmniejszą lub największą wartość. Jedna strona podziału jest wtedy pusta, więc każdy podział usuwa tylko jedną wartość, a sortowanie wymaga n(n − 1)/2 porównań. Losowy pivot lub mediana z trzech w praktyce to naprawia.

Czy sortowanie szybkie jest szybsze od sortowania przez scalanie?

W praktyce często tak: sortuje w miejscu, nie potrzebuje bufora, a jego pętla wewnętrzna jest bardzo prosta. Średnio wykonuje nieco więcej porównań niż sortowanie przez scalanie, a jego najgorszy przypadek to n², podczas gdy sortowanie przez scalanie zawsze ma n log n. Sortowania biblioteczne, takie jak introsort, zaczynają od sortowania szybkiego i przechodzą na sortowanie przez kopcowanie, gdy podziały stają się zbyt nierówne.

Czy sortowanie szybkie jest stabilne?

Nie. Podział zamienia 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 odbywa się 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