SORU
2 EKİM 2008, PERŞEMBE


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
2 EKİM 2008, PERŞEMBE


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.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • 1881 Animation

    1881 Animati

    5 EKİM 2013
  • ibebrent

    ibebrent

    23 Temmuz 2007
  • thewinekone

    thewinekone

    17 Aralık 2005