Saya mencoba memahami mengapa quicksort menggunakan partisi Lomuto dan pivot yang tetap berkinerja tidak menentu, tetapi secara keseluruhan buruk, pada input yang dihasilkan secara acak. Saya berpikir bahwa meskipun input dihasilkan secara acak, mungkin ada banyak urutan urutan, tetapi saya tidak yakin bagaimana mengukur tingkat gangguan dalam urutan. Saya berpikir untuk menggunakan jumlah inversi, tetapi saya melihat dari pertanyaan lain ini saya bertanya bahwa itu bukan ukuran yang baik dalam kasus ini.
Alasan saya menduga bahwa urutan acak saya memiliki banyak "urutan" untuk mereka adalah bahwa mengacak pivot memperbaiki masalah kinerja. Namun secara teoritis seharusnya tidak ada masalah kinerja pada urutan input yang seharusnya "acak" ini.
sumber
Jawaban:
Lomuto vs Hoare
Partisi Lomuto menderita ketika menyortir tombol yang sama, sedangkan partisi Hoare tidak.
Kedua skema partisi menderita sama ketika menggunakan pivot jauh dari median.
Mengukur gangguan
Ukuran gangguan untuk memilih untuk keperluan quicksort sederhana.
A: Seberapa jauh dihapus dari median adalah pivot tetap, dibandingkan dengan data acak?
Jika Anda bersikeras menggunakan partisi Lomuto dan jika Anda menganggap nilai duplikat diizinkan, Anda perlu menambahkan tes berikut terhadap keacakan:
B: Ada berapa banyak elemen duplikat di sana, dibandingkan dengan acak.
Tentu saja agak konyol untuk mengasumsikan bahwa nilai duplikat diperbolehkan dalam kumpulan data Anda dan masih mengevaluasi partisi Lomuto, jadi Anda mungkin harus menghilangkan duplikat sebelumnya atau beralih ke partisi Hoare atau menganggap duplikat jarang terjadi.
Kedua ukuran itu sepele untuk diukur menggunakan statistik.
Kami dapat mengesampingkan data patologis
Penyimpangan lain dari keacakan tidak akan menjadi masalah untuk keperluan analisis quicksort. Selama pivot dekat dengan median, ia akan bekerja dengan baik pada semua data yang tidak patologis.
Jarak dari acak harus benar-benar hebat untuk menjadi quicksort-patologis, sehingga kita bisa mengesampingkan itu.
Jangan pernah menggunakan pivot tetap dalam kode nyata.
Perhatikan bahwa jika Anda menulis kode real dengan pivot tetap *) (apa pun pivot itu), Anda membuka diri terhadap penolakan serangan layanan, karena penyerang dapat menyisipkan nilai patologis pada titik itu dan dengan demikian Anda harus selalu memilih elemen acak sebagai pivot.
*) atau banyak pivot jika Anda memilih x pivot terbaik.
sumber