Quicksort Partitioning: Hoare vs. Lomuto

82

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?

Robert S. Barnes
źródło
2
Nie mogę wymyślić żadnej sytuacji, w której Lomuto byłby lepszy niż Hoare. Wygląda na to, że Lomuto wykonuje dodatkowe zamiany za każdym razem A[i+1] <= x. W posortowanej tablicy (i przy rozsądnie wybranych osiach) Hoare prawie nie zamienia się, a Lomuto robi tonę (gdy j staje się wystarczająco mały, to wszystko A[j] <= x.) Czego mi brakuje?
Wandering Logic
2
@WanderingLogic Nie jestem pewien, ale wydaje się, że decyzja Cormena o zastosowaniu partycji Lomuto w jego książce może być pedagogiczna - wydaje się, że ma niezmiennie niezmienną pętlę.
Robert S. Barnes
2
Zauważ, że te dwa algorytmy nie robią tego samego. Na końcu algorytmu Hoare'a oś obrotu nie znajduje się w końcowym miejscu. Możesz dodać znak swap(A[p], A[j])na końcu Hoare, aby uzyskać takie samo zachowanie dla obu.
Aurélien Ooms
Powinieneś także sprawdzić i < jw 2 powtarzających się pętlach partycjonowania Hoare.
Aurélien Ooms
@ AurélienOoms Kod jest kopiowany bezpośrednio z książki.
Robert S. Barnes

Odpowiedzi:

92

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ń

n1n

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,,n

Metoda Lomuto

jA[j]x1,,nx1xx1x

{1,,n}1n

1nx=1n(x1)=n212.

n

Metoda Hoare'a

x

ijxij

x

Hyp(n1,nx,x1)nxx1(nx)(x1)/(n1)x

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

1nx=1n(nx)(x1)n1=n613.

(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

0ijO(nlogn)

0A[j] <= xi=nΘ(n2)

Wniosek

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

Sebastian
źródło
16
Wow, to jedna szczegółowa odpowiedź. Ładnie wykonane!
Raphael
Zgadzam się z Raphaelem, naprawdę fajna odpowiedź!
Robert S. Barnes,
1
Zrobiłbym małe wyjaśnienie, że wraz ze spadkiem stosunku unikalnych elementów do wszystkich elementów liczba porównań, które Lomuto robi, rośnie znacznie szybciej niż Hoare. Jest to prawdopodobnie spowodowane słabym podziałem ze strony Lomuto i dobrym przeciętnym podziałem ze strony Hoare.
Robert S. Barnes
Świetne wyjaśnienie dwóch metod! Dziękuję Ci!
v kouk
Możesz łatwo stworzyć wariant metody Lomuto, który może wyodrębnić wszystkie elementy równe czopowi i pozostawić je poza rekurencją, chociaż nie jestem pewien, czy to pomogłoby, czy utrudniłoby średnią wielkość liter.
Jakub Narębski
5

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ń

n1n

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

Fernando Pelliccioni
źródło