Quicksort: pivot Seçimi
Quicksort uygularken, yapmanız gereken şeylerden biri bir özet seçmektir. Ama bir kesinliği altında baktığımda, pivot seçmeliyim nasıl belli değil. Listenin ilk elemanı mı? Başka bir şey mi?
function quicksort(array)
var list less, greater
if length(array) ≤ 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ≤ pivot then append x to less
else append x to greater
return concatenate(quicksort(less), pivot, quicksort(greater))
Birisi bana farklı stratejiler için pivot ve olsun ya da olmasın farklı senaryolar bir ara seçimi kavramını kavramak yardımcı olabilir.
CEVAP
Rastgele bir pivot en kötü ihtimalle karşılaşma olasılığını en aza indirir seçerek O(n2performans (her zaman ilk veya son seçimi kötü durum neredeyse sıralanmış performans veya neredeyse ters sıralanmış neden olacak veri). Orta elemanı seçimi de çoğu durumda kabul edilebilir.
Eğer kendinizi bu uygulama ayrıca, yerinde (yani iki yeni listeler oluşturma ve sonra onları bitiştirmek olmadan) çalışan algoritma sürümü vardır.
Nasıl vi/çoklu satır seçimi başındaki ...
HTML metin tüm metin seçimi giriş tıkl...
Veri kullanarak Pivot ETMENİZ mümkün m...
Pivot üzerinde kontrolleri yok...
Yüce Metin her seçim için bir numara e...