Quicksort: pozycja obrotu po jednej partycji

Question

Czytam o quicksort, patrząc na różne implementacje i staram się owinąć mi głowę.

W this realizacji robót (które oczywiście), osią jest wybrany jako środkowego elementu a następnie lewy i prawy wskaźnik przesunie się w prawo i lewo odpowiednio, wymieniając elementy do podziału wokół przegubu.

Próbowałem tablicy [4, 3, 2, 6, 8, 1, 0].

W przypadku pierwszej partycji wartość przestawna wynosi 6, a wszystkie elementy po lewej stronie są już mniejsze niż 6, więc wskaźnik po lewej stronie zatrzyma się w osi przestawnej. Po prawej stronie zamieniamy 0 na 6, a następnie na 1 i 8, więc na końcu pierwszej iteracji tablica będzie wyglądać następująco:

[4, 3, 2, 0, 1, 8, 6].

Jednak miałem wrażenie, że po każdej iteracji w quicksort, pivot kończy się na właściwym miejscu, więc tutaj powinien się znaleźć w pozycji 5 tablicy.

Czy możliwe jest (i ok), że oś nie kończy się w poprawnej iteracji, czy jest to coś oczywistego, czego mi brakuje?

Answer 1

Istnieje wiele możliwych wariantów algorytmu quicksort. W tym przypadku jest OK, aby czop nie znajdował się we właściwym miejscu w swojej iteracji.

Cechą charakterystyczną każdej odmiany algorytmu quicksort jest to, że po etapie podziału mamy część na początku tablicy, w której wszystkie elementy są mniejsze lub równe osi obrotu, oraz część, która nie nakłada się na siebie. koniec tablicy, w której wszystkie elementy są większe lub równe obrotowi. Może być także część między nimi, gdzie każdy element jest równy obrotowi. Ten układ zapewnia, że ​​po posortowaniu lewej części i prawej części za pomocą wywołań rekursywnych i pozostawienia środkowej części w stanie nienaruszonym, cała tablica zostanie posortowana.

Zauważ, że ogólnie elementy równe pivot mogą przejść do dowolnej części tablicy. Dobra implementacja quicksort, która unika czasu kwadratowego dla najbardziej oczywistego przypadku, tj. Wszystkich równych elementów, musi rozprzestrzeniać elementy równe obrotowi między częściami racjonalnie.

Możliwe warianty obejmują:

• środkowa część zawiera tylko jeden element: obrotu. W takim przypadku pivot zajmuje ostatnie miejsce w tablicy po partycji i nie będzie używane w wywołaniach rekursywnych. To właśnie miałeś na myśli przez przestawienie swojego miejsca w iteracji. W tym podejściu dobra implementacja musi przesunąć około połowy elementów równych obrotowi do lewej części i drugiej połowie do prawej części, w przeciwnym razie mielibyśmy czas kwadratowy dla tablicy z wszystkimi równymi elementami.
• Nie ma środkowej części. Pivot i wszystkie elementy równe są rozłożone między lewą i prawą częścią. Tak właśnie działa Twoja implementacja. Jeszcze raz w tym podejściu około połowa elementów równa się czopowi powinna iść w lewą część, a druga połowa w prawą część. Można to również mieszać z pierwszą odmianą, w zależności od tego, czy sortujemy tablicę z parzystą, czy nieparzystą liczbą elementów.
• Każdy element równy pivot przechodzi do środkowej części. Nie ma elementów równych obrotowi w lewej lub prawej części. To całkiem wydajne i to jest przykład, który daje rozwiązanie problemu równego wszystkim elementom. Tablice ze wszystkimi równymi sobie elementami sortowane są w czasie liniowym.

W związku z tym poprawna i skuteczna implementacja quicksortu jest dość skomplikowana (istnieje również problem z wyborem dobrej osi obrotu, dla której istnieje kilka podejść z różnymi kompromisami, lub z optymalizacją przełączenia na inną algorytm sortowania rekursywnego dla mniejszych rozmiarów podrozdziałów).

Ponadto, wydaje się, że realizacja jesteś związana, może zrobić wywołań rekurencyjnych na nakładających subarrays:

if (i <= j) { 
    exchange(i, j); 
    i++; 
    j--; 
} 

Na przykład, gdy i jest równa j, te elementy zostaną zamienione, a i staną większa niż j o 2. Po tym 3 elementy będą nakładać się między zakresami następujących wywołań rekursywnych. Kod nadal działa jednak poprawnie.