Apa keuntungan Quicksort Acak?

Dalam buku mereka Randomized Algorithms , Motwani dan Raghavan membuka pengantar dengan deskripsi fungsi RandQS mereka - Randoms quicksort - di mana pivot, yang digunakan untuk mempartisi himpunan menjadi dua bagian, dipilih secara acak.

Saya telah memeras otak saya (diakui agak kurang bertenaga) atas hal ini selama beberapa waktu, tetapi saya belum dapat melihat keuntungan apa yang dimiliki algoritme ini hanya dengan memilih, katakanlah, elemen tengah (dalam indeks, bukan ukuran) setiap kali.

Saya kira apa yang tidak bisa saya lihat adalah ini: jika set awal dalam urutan acak, apa perbedaan antara memilih elemen di lokasi acak di set dan memilih elemen pada posisi tetap?

Bisakah seseorang mencerahkan saya, dalam istilah yang cukup sederhana?

Jika array input didistribusikan secara acak, maka (seperti yang Anda catat) tidak ada perbedaan antara selalu memilih elemen pada posisi tetap (misalnya yang tengah seperti yang Anda sarankan) atau memilih elemen yang dipilih secara acak.

Namun jika array input Anda tidak benar-benar dalam urutan acak (yang terjadi pada hampir semua skenario praktis) maka kita perlu "preshufle" array agar elemen di dalamnya ditempatkan dalam urutan acak, atau ( setara) selalu mengambil elemen acak sebagai poros. Ini memastikan fase partisi dari quicksort mempartisi array ke dalam sub-array dengan ukuran yang hampir sama dan karenanya waktu berjalan yang diharapkan tetap $O(n\log n)$

Jadi kebingungan Anda tampaknya berasal dari fakta bahwa entah bagaimana Anda menganggap algoritma pengurutan dapat (dalam praktiknya) mengharapkan array input untuk selalu didistribusikan secara acak.

Seperti dicatat oleh Jernej, asumsi bahwa semua permutasi dari input sama kemungkinan tidak selalu berlaku dalam kenyataan. Gagasan pertama mungkin untuk mengubah array input. Ini akan berhasil, tetapi lebih mudah untuk menganalisis situasi di mana pivot dipilih secara acak. Ini juga dikenal sebagai pengambilan sampel acak .