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

  • Juan Carlos Candela Bordera

    Juan Carlos

    4 Mart 2009
  • katherine gomez

    katherine go

    1 Aralık 2011
  • Top10Series

    Top10Series

    26 Kasım 2008