Kısmi sıralama - Partial sorting

Olarak bilgisayar biliminin , kısmi sıralama a, rahat varyantı ayırma sorunu. Kısmi sıralama listesini dönen iken toplam sıralama, onun elemanları tüm sırayla görünür böyle öğelerin bir listesini dönen sorunudur k en küçük (veya k en büyük) sırayla elemanları. (Yukarıda diğer elemanlar k küçük olanları), aynı zamanda, yerinde kısmi tür olarak, depolanabilir veya kısmen türlü akış yaygın olan, atılabilir. Kısmi sıralama yaygın bir uygulama örneği, bir liste "Top-100" işlem olup.

Her dizin için kısmen sıralı listede endeksleri açısından, içinde ben 1 ila k, i -inci elemanı tam olarak sıralanmış listesinde olacağını aynı yerde geçerli: eleman i kısmen sıralı listenin içerdiği sıra istatistiğini ı giriş listesinin.

Çevrim sorun

Öbek bazlı solüsyon

Yığınlar , basit bir tek-geçişli kısmi tür kabul $k$ sabitlenir: ilk kağıdı $k$ max-yığın girdi elemanları. Ardından, kalan elemanlar üzerinden bir pas sırayla yığın her ekleyin ve en büyük elemanı çıkarın. Her ekleme işlemi alır $O (log k)$ ile sonuçlanan, bir zaman $O (n, log k)$ toplam zaman; Bu algoritma küçük değerleri için pratiktir $k$ ve çevrimiçi ayarlara. Başka seçenekler (build alır tüm değerler için bir min-yığın oluşturmaktır $Ç (n)$ her kaldırmak operasyon alır) ve yığın K kez kafasını çıkarıp $O (log n)$ . Bu durumda algoritma alır $O (n + klog N)$ .

bölümleme seçimiyle Çözüm

Sadece bir liste gerektiren bir başka gevşeme $k$ en küçük elementler, ancak bu sipariş gerekmeden, hiç sorun eşdeğer kılan bölüm tabanlı seçimi ; Orijinal kısmi ayırma sorun, ilk olarak bir dizi elde etmek için bu tür bir seçme algoritması ile çözülebilir $k$ elemanlarıdır $k$ bir toplam maliyeti, en küçük ve bu sıralama $O (n + k günlük k)$ işlemleri. Bu algoritma düzeni uygulamak popüler bir seçimdir birleştirmektir QuickSelect ve quicksort ; Sonuç bazen "quickselsort" denir.

Uzmanlaşmış sıralama algoritmaları

Yukarıda belirtilen daha verimli göre özel bir kısmi ayırma algoritmaları MergeSort ve hızlı sıralama . Quicksort varyantında, yinelemeli sonra düşeceği unsurları içeren bölümleri sıralamak için gerek yoktur $k$ ( 'sol' sınır başlayarak) nihai sıralanmış diziye yerde inci'. Pivot pozisyonu düşerse Böylece $k$ ya da geç, biz sadece sol bölümünde Recurse:

 function partial_quicksort(A, i, j, k)
     if i < j
         p ← pivot(A, i, j)
         p ← partition(A, i, j, p)
         partial_quicksort(A, i, p-1, k)
         if p < k-1
             partial_quicksort(A, p+1, j, k)

Elde edilen algoritma kısmi quicksort denilen ve bir gerektirir beklenen sadece zaman $O (n + k günlük k)$ , ve özellikle de, uygulamada oldukça etkilidir seçim sıralama olduğunda bir baz olarak kullanılabilir durumda olan $K$ göre küçük olur $n$ . Ancak, en kötü durum zaman karmaşıklığı kötü Pivot seçimi söz konusu olduğunda, hala çok kötü. En kötü durum doğrusal zaman seçim algoritmasının çizgisinde Pivot seçimi iyi kötü durum performansı almak için kullanılabilir.

Artan sıralama

Artan sıralama giriş ön vazgeçmiş ancak kısmi sıralama problemi, bir "çevrimiçi" versiyonu $k$ bilinmemektedir: Belirli bir $k$ -sorted dizi, dizi olması için kısmen sıralı kısmını uzatmak mümkün olmalıdır $(k 1)$ -sorted.

Yığın bir yol $O (n + k günlük n)$ çevrimiçi kısmi sıralama çözüm: İlk "heapify", lineer zamanda, tam giriş dizisi min-yığın üretir. Ardından yığın minimum ayıklamak $k$ süreleri.

Bir asimptotik hızlı artan sıralama QuickSelect değiştirerek elde edilebilir. Nedeniyle Paredes ve Navarro versiyonu muhafaza yığın artımlı sıralama sürekli bir dizi küçük madde talep ile gerçekleştirilebilir, böylece çağrı boyunca pivotların $A$ aşağıdaki algoritma:

Algoritma $IQS (A : dizi, i : tamsayıdır S : Yığın)$ döner $i$ 'inci küçük elemanı $A$

Eğer i = üst ( S ) :
- Pop $S$
- Dönüş $bir [i]$
Let $eksen \leftarrow rastgele [I, üst (S))$
Güncelleştirme $eksen \leftarrow bölüm (A [I : üst (S)), bir [eksen])$
İtin $Pivot$ üzerine $S$
Dönüş $IQS (A, I, S)$

Yığın $S$ sadece uzunluk içeren başlatıldı $n$ bir $A$ . $k$ dizi -sıralama çağırarak yapılmaktadır $IQS (A, I, S)$ için $i = 0, 1, 2, ...$ ; aramaların bu dizi sahip ortalama durum karmaşıklığı $O (n + k günlük k)$ . En kötü durum zaman kuadratik, ama bu tarafından rastgele eksen seçimini değiştirerek düzeltilebilir medyan ortanca algoritması.

Dil / kütüphane desteği

C ++ standart olarak adlandırılan bir kütüphane işlevi belirtir std::partial_sort.
Python standart kütüphane işlevleri içerir nlargestve nsmallestonun içinde heapqmodül.
Julia standart kütüphanesi içerir PartialQuickSortuygulanmasını.

Languages

In other projects