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

  • LaKe Lightroom Tutorials

    LaKe Lightro

    22 Temmuz 2014
  • LiteralMSPaint

    LiteralMSPai

    27 EKİM 2010
  • TechShowsYou

    TechShowsYou

    3 Mart 2011