Istnieją dwie metody partycji Quicksort wymienione w Cormen:

Hoare-Partition(A, p, r)
x = A[p]
i = p - 1
j = r + 1
while true
    repeat
        j = j - 1
    until A[j] <= x
    repeat
        i = i + 1
    until A[i] >= x
    if i < j
        swap( A[i], A[j] )
    else
        return j

i:

Lomuto-Partition(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        swap( A[i], A[j] )
swap( A[i +1], A[r] )
return i + 1

Niezależnie od metody wyboru osi przestawnej, w jakich sytuacjach jedna jest lepsza od drugiej? Wiem na przykład, że Lomuto działa stosunkowo słabo, gdy występuje wysoki odsetek zduplikowanych wartości (tj. Gdy powiedzmy, że więcej niż 2/3 tablica ma taką samą wartość), gdzie Hoare dobrze sobie radzi w tej sytuacji.

Jakie inne specjalne przypadki sprawiają, że jedna metoda partycji jest znacznie lepsza od drugiej?

Wymiar pedagogiczny

Ze względu na swoją prostotę metoda partycjonowania Lomuto może być łatwiejsza do wdrożenia. Jest ładna anegdota w Perle programowania Jona Bentleya na temat sortowania:

„Większość dyskusji na temat Quicksort wykorzystuje schemat partycjonowania oparty na dwóch zbliżających się indeksach [...] [tj. Hoare'a]. Chociaż podstawowa idea tego schematu jest prosta, zawsze uważałem szczegóły za trudne - kiedyś spędziłem większą część dwóch dni, ścigając błąd ukryty w krótkiej pętli partycjonowania. Czytelnik wstępnego szkicu skarżył się, że standardowa metoda z dwoma indeksami jest w rzeczywistości prostsza niż metoda Lomuto, i naszkicował trochę kodu, aby o tym powiedzieć; Przestałem się zajmować, gdy znalazłem dwa błędy. ”

Wymiar wydajności

Dla praktycznego zastosowania łatwość wdrożenia może być poświęcona ze względu na wydajność. Na podstawie teoretycznej możemy określić liczbę porównań elementów i zamian w celu porównania wydajności. Ponadto na rzeczywisty czas działania będą mieć wpływ inne czynniki, takie jak wydajność buforowania i nieprzewidywalne oddziały.

Jak pokazano poniżej, algorytmy zachowują się bardzo podobnie w przypadkowych kombinacjach, z wyjątkiem liczby zamian . Tam Lomuto potrzebuje trzy razy tyle co Hoare!

Liczba porównań

$n-1$$n$

Liczba zamian

Liczba zamian jest losowa dla obu algorytmów, w zależności od elementów w tablicy. Jeśli założymy przypadkowe permutacje , tj. Wszystkie elementy są różne i każda permutacja elementów jest jednakowo prawdopodobna, możemy przeanalizować oczekiwaną liczbę zamian.

$1,\ldots,n$

Metoda Lomuto

$j$$A[j]$$x$$1,\ldots,n$$x-1$$x$$x-1$$x$

$\{1,\ldots,n\}$$\frac1n$

$n$

Metoda Hoare'a

$x$

$i$$j$$x$$i$$j$

$x$

$\mathrm{Hyp}(n-1,n-x,x-1)$$n-x$$x-1$$(n-x)(x-1)/(n-1)$$x$

Na koniec uśredniamy ponownie wszystkie wartości przestawne, aby uzyskać ogólną oczekiwaną liczbę zamian partycjonowania Hoare:

(Bardziej szczegółowy opis można znaleźć w mojej pracy magisterskiej , strona 29.)

Wzorzec dostępu do pamięci

Oba algorytmy używają dwóch wskaźników do tablicy, które skanują ją sekwencyjnie . Dlatego oba zachowują się prawie optymalnie w buforowaniu wrt.

Równe elementy i już posortowane listy

Jak już wspomniano w Wandering Logic, wydajność algorytmów różni się bardziej drastycznie w przypadku list, które nie są przypadkowymi kombinacjami.

$n/2$

$0$$i$$j$$\mathcal O(n\log n)$

$0$A[j] <= x$i=n$$\Theta(n^2)$

Wniosek

Metoda Lomuto jest prosta i łatwiejsza do wdrożenia, ale nie powinna być stosowana do implementacji metody sortowania bibliotek.

Niektóre komentarze zostały dodane do doskonałej odpowiedzi Sebastiana.

Omówię ogólnie algorytm przestawiania partycji, a nie jego szczególne zastosowanie w Quicksort .

Stabilność

Algorytm Lomuto jest półstabilny : zachowana jest względna kolejność elementów niespełniających predykatu . Algorytm Hoare'a jest niestabilny.

Wzorzec dostępu do elementu

Algorytmu Lomuto można używać z pojedynczo połączoną listą lub podobnymi strukturami danych tylko do przodu. Algorytm Hoare wymaga dwukierunkowości .

Liczba porównań

$n-1$$n$

Ale aby to zrobić, musimy poświęcić 2 właściwości:

1. Sekwencja, która ma być podzielona na partycje, nie może być pusta.
2. Algorytm nie może zwrócić punktu podziału.

$n$