Apa yang membuat kasus buruk untuk penyortiran cepat?

10

Saya belajar tentang quicksort dan ingin mengilustrasikan berbagai array yang sulit dimiliki quicksort. Quicksort yang saya pikirkan tidak memiliki pengocokan acak awal, partisi 2, dan tidak menghitung median.

Saya memikirkan tiga contoh sejauh ini: 

[1,2,3,4,5,6,7,8,9,10] - when the array is sorted
[10,9,8,7,6,5,4,3,2,1] - when the array is reversed
[1,1,1,1,1,1,1,1,1,1] - when the array is the same values
[1,1,1,2,2,2,3,3,3,3] - when there are few and unique keys

Misalnya, saya tidak terlalu yakin tentang yang ini: 

[1,3,5,7,9,10,8,6,4,2]

Jadi apa yang membuat array yang quicksort mengalami kesulitan dibandingkan dengan yang cepat (hampir) ideal?

algorithms sorting mrQWERTY
sumber
2
Bagaimana pivot dipilih? Anda menyatakan dua cara itu tidak dipilih, tetapi tidak bagaimana itu dipilih.
Winston Ewert
Tolong beri kasus terburuk untuk QuickSort - kapan itu bisa terjadi? pada StackOverflow baca. Saya juga menemukan sorting.at menjadi visualisasi yang bagus dari algoritma sorting.
@WinstonEwert Pivot dipilih oleh elemen pertama.
mrQWERTY
@ Renren29 Saya telah memodifikasi pertanyaan sedikit mencoba untuk memindahkannya untuk fokus pada alasan mengapa quicksort akan mengalami kesulitan dengan array yang diberikan daripada mencari array contoh (saya tidak orang memberi Anda jawaban [2,1,2,1,2,1,2,1]dan itu menjadi keseluruhan menjawab). Tujuan dari pertanyaan itu adalah, idealnya, menjadi tempat di mana orang lain dapat datang dan mencari tahu lebih banyak tentang mengapa (yang memiliki jawaban) daripada contoh (yang jumlahnya tak terhitung).
Anda menjalankan quicksort ke potongan 2 elemen? Karena implementasi dunia nyata cenderung menggunakan jenis yang lebih sederhana untuk bongkahan kecil. Misalnya, bandingkan-dan-tukar jauh lebih sederhana daripada quicksort untuk N = 2.
MSalters

Jawaban:

8

Setiap algoritma memiliki kasus terburuk, dan dalam banyak kasus kasus terburuk benar-benar buruk sehingga layak untuk diuji. Masalahnya adalah, tidak ada kasus terburuk tunggal hanya karena Anda tahu algoritma dasar.

Kasus terburuk yang umum termasuk: sudah diurutkan; diurutkan secara terbalik; hampir disortir, satu elemen rusak; semua nilai sama; semua sama kecuali pertama (atau terakhir) lebih tinggi (atau lebih rendah). Kami pernah memiliki semacam kasus di mana kasus terburuk adalah pola gigi gergaji tertentu, yang sangat sulit untuk diprediksi tetapi cukup umum dalam praktiknya.

Kasus terburuk untuk quicksort adalah salah satu yang membuatnya selalu memilih poros paling buruk, sehingga salah satu partisi hanya memiliki satu elemen. Jika pivot adalah elemen pertama (pilihan buruk) maka data yang sudah diurutkan atau dibalik adalah kasus terburuk. Untuk median-dari-tiga data pivot yang semuanya sama atau hanya yang pertama atau terakhir berbeda lakukan triknya.

Untuk quicksort kompleksitas rata-rata adalah nlogn dan kasus terburuk adalah n ^ 2. Alasan mengapa layak memicu perilaku kasus terburuk adalah karena ini juga merupakan kasus yang menghasilkan kedalaman rekursi terbesar. Untuk implementasi yang naif, kedalaman rekursi bisa n, yang dapat memicu stack overflow. Menguji situasi ekstrem lainnya (termasuk kasus terbaik) mungkin bermanfaat untuk alasan serupa.

david.pfx
sumber
Begitu ya, jadi deviasi standar dari mean benar-benar menentukan hasil partisi.
mrQWERTY
"... dan dalam hampir setiap kasus kasus terburuk benar-benar buruk sehingga layak untuk diuji." . Itu bisa diperdebatkan. Ketika saya melihat tabel ini: en.wikipedia.org/wiki/… Saya menyimpulkan bahwa untuk kebanyakan algoritma pengurutan "baik" (yaitu dengan O(NlogN)kinerja rata-rata atau lebih baik) kasus terburuk dan rata-rata memiliki kompleksitas yang sama. Itu menunjukkan bahwa biasanya TIDAK layak pengujian untuk kasus terburuk. (Mengingat bahwa tes itu mungkin O(N)... atau lebih buruk.)
Stephen C
@ Renren29: Median 3 pivot akan menjadi yang pertama atau terakhir hanya jika 2 atau 3 nilainya sama. SD tidak masuk ke dalamnya.
david.pfx
@StephenC: Banyak algoritma 'baik' termasuk quicksort memiliki kompleksitas kasus terburuk. Tapi lihat sunting.
david.pfx
@ david.pfx - "Some" ... YES. "Hampir setiap" ... TIDAK.
Stephen C
0

Algoritma lolos dari kebanyakan kasus buruk menggunakan pivot acak, mengecualikan elemen kontinu sama dengan pivot dari partisi, dan pencarian asimetris. Itu mencari maju elemen lebih besar atau sama dengan pivot, dan mencari mundur elemen kurang dari pivot.
Saya berterima kasih kepada MichaelT, pencarian Asimetris dirancang untuk menyelesaikan [2,1,2,1,2,1,2,1].

Hasil berikut dihasilkan oleh fungsi saya qsort_random (). N = 100.000 

usec    call   compare   copy    pattern
80132   62946  1971278   877143  random
47326   57578  1606067   215155  sorted : 0,1,2,3,...,n-1
49927   63578  1628883   338715  sorted in reverse : n-1,n-2,...,2,1,0
55619   63781  1596934   377330  nearly reverse : n-2,n-1,n-4,n-3,...,2,3,0,1
54714   66667  1611454   290392  median-3-killer : n-1,0,1,2,...,n-2
1491    1      99999     4       all values the same : n,n,n,...
1577    1      99999     4       first is higher : n,1,1,1,...
2778    2      156159    10      last is lower : n,n,n,...,n,1
2994    3      199996    100009  a few data : n,...,n,1,...,1
3196    3      199996    50012   zigzag : n,1,n,1,...,n,1
917796  56284  67721985  673356  valley(sawtooth?) : n-1,n-3,...,0,...,n-4,n-2

Sebagian besar kasus lebih cepat daripada pola acak. Pola lembah adalah kasus yang buruk untuk sebagian besar pemilihan poros. 

qsort(3)       usec = 14523   call = 0      compare = 884463    copy = 0
qsort_head()   usec = 138609  call = 99999  compare = 8120991   copy = 1214397
qsort_middle() usec = 664325  call = 99999  compare = 52928111  copy = 1036047
qsort_trad()   usec = 118122  call = 99999  compare = 6476025   copy = 1337523
qsort_random() usec = 295699  call = 58806  compare = 19439952  copy = 732962
qsort_log2()   usec = 66411   call = 63987  compare = 1597455   copy = 944821

qsort_log2 () keluar dari kasus buruk dengan memilih pivot di elemen log2 (N).
qsort (3) menggunakan perpustakaan GNU yang merupakan semacam pengurutan indeks.
qsort_trad () pilih pivot di elemen pertama, tengah dan terakhir.
qsort_random () dan qsort_log2 () tidak menggunakan swapping.
Sumber C program dan skrip diposting di github .

Leorge Takeuchi
sumber