Ada dua metode partisi quicksort yang disebutkan dalam 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

dan:

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

Mengabaikan metode pemilihan poros, dalam situasi apa yang lebih disukai dari yang lain? Saya tahu, misalnya, bahwa Lomuto membentuk relatif buruk ketika ada persentase tinggi dari nilai duplikat (yaitu di mana katakanlah lebih dari 2 / 3rds array adalah nilai yang sama), di mana Hoare berkinerja baik dalam situasi itu.

Kasus khusus apa lagi yang membuat satu metode partisi lebih penting daripada yang lainnya?

Dimensi Pedagogis

Karena kesederhanaannya, metode partisi Lomuto mungkin lebih mudah diimplementasikan. Ada anekdot yang bagus dalam Mutiara Pemrograman Jon Bentley tentang Penyortiran:

“Sebagian besar diskusi Quicksort menggunakan skema partisi berdasarkan dua indeks yang mendekati [...] [yaitu Hoare's]. Meskipun ide dasar dari skema itu sangat mudah, saya selalu menemukan detailnya rumit - saya pernah menghabiskan bagian yang lebih baik dari dua hari mengejar bug yang bersembunyi di loop partisi pendek. Seorang pembaca rancangan awal mengeluh bahwa metode dua indeks standar sebenarnya lebih sederhana daripada Lomuto dan membuat sketsa beberapa kode untuk menjelaskan maksudnya; Saya berhenti merawat setelah menemukan dua bug. ”

Dimensi Kinerja

Untuk penggunaan praktis, kemudahan implementasi mungkin dikorbankan demi efisiensi. Secara teori, kita dapat menentukan jumlah perbandingan elemen dan swap untuk membandingkan kinerja. Selain itu, waktu berjalan aktual akan dipengaruhi oleh faktor-faktor lain, seperti kinerja caching dan mispredictions cabang.

Seperti yang ditunjukkan di bawah ini, algoritma berperilaku sangat mirip pada permutasi acak kecuali untuk jumlah swap . Di sana Lomuto membutuhkan tiga kali lipat dari Hoare!

Jumlah perbandingan

Kedua metode dapat diimplementasikan menggunakan perbandingan untuk mempartisi array dengan panjang . Ini pada dasarnya optimal, karena kita perlu membandingkan setiap elemen dengan pivot untuk memutuskan di mana harus meletakkannya.$n-1$$n$

Jumlah Swap

Jumlah swap adalah acak untuk kedua algoritma, tergantung pada elemen dalam array. Jika kita mengasumsikan permutasi acak , yaitu semua elemen berbeda dan setiap permutasi elemen sama kemungkinannya, kita dapat menganalisis jumlah swap yang diharapkan .

Karena hanya urutan relatif yang dihitung, kami mengasumsikan bahwa elemen-elemennya adalah angka . Itu membuat diskusi di bawah ini lebih mudah karena peringkat elemen dan nilainya bertepatan.$1,\ldots,n$

Metode Lomuto

Variabel indeks memindai seluruh array dan setiap kali kami menemukan elemen lebih kecil dari pivot , kami melakukan swap. Di antara elemen , tepatnya yang lebih kecil dari , jadi kita mendapatkan swap jika pivotnya .$j$$A[j]$$x$$1,\ldots,n$$x-1$$x$$x-1$$x$

Harapan keseluruhan kemudian dihasilkan dengan rata-rata di atas semua pivot. Setiap nilai dalam memiliki kemungkinan yang sama untuk menjadi pivot (yaitu dengan prob. ), jadi kita harus$\{1,\ldots,n\}$$\frac1n$

swap rata-rata untuk mempartisi array panjang dengan metode Lomuto.$n$

Metode Hoare

Di sini, analisisnya sedikit lebih rumit: Bahkan memperbaiki pivot , jumlah swap tetap acak.$x$

Lebih tepatnya: Indeks dan berjalan ke arah satu sama lain sampai mereka bersilangan, yang selalu terjadi pada (dengan kebenaran algoritma partisi Hoare!). Ini secara efektif membagi array menjadi dua bagian: Bagian kiri yang dipindai oleh dan bagian kanan dipindai oleh .$i$$j$$x$$i$$j$

Sekarang, swap dilakukan tepat untuk setiap pasangan elemen "salah tempat", yaitu elemen besar (lebih besar dari , dengan demikian termasuk dalam partisi kanan) yang saat ini terletak di bagian kiri dan elemen kecil terletak di bagian kanan. Perhatikan bahwa pembentukan pasangan ini selalu berhasil, yaitu ada jumlah elemen kecil yang awalnya di bagian kanan sama dengan jumlah elemen besar di bagian kiri.$x$

Satu dapat menunjukkan bahwa jumlah pasangan ini terdistribusi secara hypergeometrik : Untuk elemen besar kita secara acak menggambar posisi mereka dalam array dan memiliki posisi di bagian kiri. Dengan demikian, jumlah pasangan yang diharapkan adalah mengingat bahwa pivot adalah .$\mathrm{Hyp}(n-1,n-x,x-1)$$n-x$$x-1$$(n-x)(x-1)/(n-1)$$x$

Terakhir, kami rata-rata lagi atas semua nilai pivot untuk mendapatkan jumlah swap yang diharapkan secara keseluruhan untuk partisi Hoare:

(Penjelasan lebih rinci dapat ditemukan dalam tesis master saya , halaman 29.)

Pola Akses Memori

Kedua algoritma menggunakan dua pointer ke array yang memindai secara berurutan . Oleh karena itu keduanya berperilaku ctc hampir optimal.

Elemen yang Sama dan Daftar yang Sudah Disortir

Seperti yang telah disebutkan oleh Wandering Logic, kinerja algoritma berbeda lebih drastis untuk daftar yang bukan permutasi acak.

Pada array yang sudah diurutkan, metode Hoare tidak pernah bertukar, karena tidak ada pasangan yang salah tempat (lihat di atas), sedangkan metode Lomuto masih melakukan kira-kira swap!$n/2$

Kehadiran elemen yang sama membutuhkan perawatan khusus di Quicksort. (Saya sendiri masuk ke perangkap ini; lihat tesis master saya , halaman 36, untuk “Tale on Premature Optimization”) Pertimbangkan sebagai contoh ekstrim array yang diisi dengan s. Pada array seperti itu, metode Hoare melakukan swap untuk setiap pasangan elemen - yang merupakan kasus terburuk untuk partisi Hoare - tetapi dan selalu bertemu di tengah array. Dengan demikian, kami memiliki partisi optimal dan total waktu berjalan tetap dalam .i j O ( n log n $0$$i$$j$$\mathcal O(n\log n)$

Metode Lomuto berperilaku jauh lebih bodoh pada semua array : Perbandingannya akan selalu benar, jadi kami melakukan swap untuk setiap elemen ! Tetapi yang lebih buruk: Setelah loop, kita selalu memiliki , jadi kami mengamati partisi terburuk, membuat kinerja keseluruhan menurun ke !i = n Θ ( n 2$0$A[j] <= x$i=n$$\Theta(n^2)$

Kesimpulan

Metode Lomuto sederhana dan lebih mudah diimplementasikan, tetapi tidak boleh digunakan untuk menerapkan metode penyortiran perpustakaan.

Beberapa komentar ditambahkan ke jawaban Sebastian yang luar biasa.

Saya akan berbicara tentang algoritma pengaturan ulang partisi secara umum dan bukan tentang penggunaan khusus untuk Quicksort .

Stabilitas

Algoritma Lomuto adalah semistable : urutan relatif dari elemen-elemen yang tidak memenuhi predikat dipertahankan. Algoritma Hoare tidak stabil.

Pola Akses Elemen

Algoritma Lomuto dapat digunakan dengan daftar yang ditautkan secara tunggal atau struktur data hanya-maju yang serupa. Algoritme Hoare membutuhkan dua arah .

Jumlah perbandingan

Algoritma Lomuto dapat diimplementasikan dengan melakukan aplikasi dari predikat untuk mempartisi urutan panjang . (Hoare juga).$n-1$n$n$

Tetapi untuk melakukan ini kita harus mengorbankan 2 properti:

1. Urutan yang akan dipartisi tidak boleh kosong.
2. Algoritma tidak dapat mengembalikan titik partisi.

Jika kita membutuhkan salah satu dari 2 properti ini, kita tidak punya pilihan selain mengimplementasikan algoritma dengan membuat perbandingan .$n$