Kova sıralama - Bucket sort

kova sıralama

Sınıf	sıralama algoritması
Veri yapısı	Dizi
En kötü durum performansı	${\displaystyle O\sol(n\log(n)\sağ)}$
Ortalama performans	${\displaystyle O\sol(n+{\frac {n^{2}}{k}}+k\sağ)}$, burada k kova sayısıdır. .${\displaystyle O(n),{\text{ne zaman }}k\yaklaşık n}$
En kötü durum alanı karmaşıklığı	${\görüntüleme stili O(n+k)}$

Öğeler kutular arasında dağıtılır

Ardından, öğeler her bölmede sıralanır

Kova sıralama veya bin sıralama , bir dizinin öğelerini birkaç kovaya dağıtarak çalışan bir sıralama algoritmasıdır . Daha sonra her bir kova, ya farklı bir sıralama algoritması kullanılarak ya da kova sıralama algoritmasının yinelemeli bir şekilde uygulanmasıyla ayrı ayrı sıralanır. Bu bir dağıtım sıralamasıdır , güvercin deliği sıralamasının bir genellemesidir ve en az anlamlı basamak lezzetinde sayı tabanı sıralamasının kuzenidir . Kova sıralama, karşılaştırmalarla uygulanabilir ve bu nedenle bir karşılaştırmalı sıralama algoritması olarak da düşünülebilir . Hesaplama karmaşıklığı , her kepçe, kullanımına bölüm sayısını sıralamak için kullanılan algoritma bağlıdır ve giriş eşit dağılmış olup olmadığını gösterir.

Kova sıralama şu şekilde çalışır:

1. Başlangıçta boş olan bir dizi "kova" ayarlayın.
2. Scatter : Her nesneyi kendi kovasına koyarak orijinal dizinin üzerinden geçin.
3. Boş olmayan her bir kovayı sıralayın.
4. Topla : Kovaları sırayla ziyaret edin ve tüm öğeleri orijinal diziye geri koyun.

sözde kod

function bucketSort(array, k) is
    buckets ← new array of k empty lists
    M ← the maximum key value in the array
    for i = 1 to length(array) do
        insert array[i] into buckets[floor(k × array[i] / M)]
    for i = 1 to k do 
        nextSort(buckets[i])
    return the concatenation of buckets[1], ...., buckets[k]

Dizi edelim dizinin göstermektedirler sıralı ve olmaya k kullanımına kovalar anlamında olabildikleri sayısı. Tüm anahtarlar bir kez yinelenerek maksimum anahtar değeri doğrusal zaman hesaplanabilir . Kat fonksiyonu bir tam sayıya kayan sayı dönüştürmek için kullanılır (ve muhtemelen çok veri türlerini döküm) olmalıdır. nextSort işlevi , her bir kovayı sıralamak için kullanılan bir sıralama işlevidir. Geleneksel olarak, eklemeli sıralama kullanılır, ancak seçim sıralama veya birleştirme sıralama gibi diğer algoritmalar da kullanılabilir . KovaSort'un kendisini nextSort olarak kullanmak, sayı tabanı sıralamasının bir görelisini üretir ; özellikle, n = 2 durumu hızlı sıralamaya karşılık gelir (potansiyel olarak zayıf pivot seçenekleriyle olsa da).

analiz

En kötü durum analizi

Girdi, birbirine yakın (kümeleme) birkaç anahtar içerdiğinde, bu öğelerin aynı kovaya yerleştirilmesi muhtemeldir, bu da bazı grupların ortalamadan daha fazla öğe içermesine neden olur. En kötü durum senaryosu, tüm öğeler tek bir kovaya yerleştirildiğinde ortaya çıkar. Daha sonra genel performansa, örneğin eklemeli sıralama veya birleştirmeli sıralama gibi karşılaştırmalı sıralama algoritmaları gibi her bir kovayı sıralamak için kullanılan algoritma hakim olacaktır . ${\ Displaystyle O(n^{2})}$ ${\ Displaystyle O(n\log(n))}$

Ortalama durum analizi

Girdinin eşit olarak dağıtıldığı durumu düşünün. İlk aşama, initialize kova ve en fazla anahtar değerini bulmak dizide, yapılabilir zaman. Bölme ve çarpma sabit zamanda yapılabilir, o zaman saçılım da maliyeti onun kova her elemanı . Sıralama ekleme varsayalım her kova, daha sonra üçüncü aşama maliyetleri sıralamak için kullanılır , endeksli kovanın uzunluğu . Ortalama süre ile ilgili olduğumuz için, bunun yerine beklentinin değerlendirilmesi gerekiyor. Öğenin kovaya yerleştirilmesi ve aksi takdirde rastgele değişken olsun . Biz var . Öyleyse, ${\görüntüleme stili O(n)}$${\görüntüleme stili O(n)}$${\displaystyle O(\textstyle \sum _{i=1}^{k}\displaystyle n_{i}^{2})}$${\displaystyle n_{i}}$${\görüntüleme stili ben}$${\ Displaystyle E(n_{i}^{2})}$${\displaystyle X_{ij}}$${\görüntüleme stili 1}$${\görüntüleme stili j}$${\görüntüleme stili ben}$${\görüntüleme stili 0}$${\displaystyle n_{i}=\sum _{j=1}^{n}X_{ij}}$

${\displaystyle {\begin{aligned}E(n_{i}^{2})&=E\left(\sum _{j=1}^{n}X_{ij}\sum _{k=1} ^{n}X_{ik}\sağ)\\&=E\left(\sum _{j=1}^{n}\sum _{k=1}^{n}X_{ij}X_{ik }\right)\\&=E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k \leq n}\sum _{j\neq k}X_{ij}X_{ik}\sağ)\end{hizalı}}}$

Son satır, toplamı vaka ve vaka olarak ayırır . Kepçeye dağıtılmış bir nesnenin şansı yana olan , olasılıkla 1 ve 0 olacaktır. ${\görüntüleme stili j=k}$${\görüntüleme stili j\neq k}$${\görüntüleme stili ben}$${\ Displaystyle 1/k}$${\displaystyle X_{ij}}$${\ Displaystyle 1/k}$

${\displaystyle E(X_{ij}^{2})=1^{2}\cdot \left({\frac {1}{k}}\sağ)+0^{2}\cdot \left(1 -{\frac {1}{k}}\sağ)={\frac {1}{k}}}$

${\displaystyle E(X_{ij}X_{ik})=1\cdot \left({\frac {1}{k}}\sağ)\sol({\frac {1}{k}}\sağ) ={\frac {1}{k^{2}}}}$

Toplama ile, olurdu

${\displaystyle E\left(\sum _{j=1}^{n}X_{ij}^{2}\sağ)+E\left(\sum _{1\leq j,k\leq n}\ toplam _{j\neq k}X_{ij}X_{ik}\sağ)=n\cdot {\frac {1}{k}}+n(n-1)\cdot {\frac {1}{k ^{2}}}={\frac {n^{2}+nk-n}{k^{2}}}}$

Son olarak, karmaşıklık olacaktır . ${\displaystyle O\left(\sum _{i=1}^{k}E(n_{i}^{2})\sağ)=O\left(\sum _{i=1}^{k} {\frac {n^{2}+nk-n}{k^{2}}}\sağ)=O\sol({\frac {n^{2}}{k}}+n\sağ)}$

Her bir kovadaki tüm sıralanmış nesneleri bir araya getiren kova sıralamanın son adımı zaman gerektirir . Bu nedenle, toplam karmaşıklık . k olarak seçilirse , kepçe sıralamanın düzgün dağılmış bir girdi verildiğinde ortalama sürede çalıştığını unutmayın . ${\görüntüleme stili O(k)}$${\displaystyle O\sol(n+{\frac {n^{2}}{k}}+k\sağ)}$${\görüntüleme stili k=\Teta (n)}$${\görüntüleme stili O(n)}$

Optimizasyonlar

Ortak bir optimizasyon kovalar sıralanmamış elemanları orijinal dizideki geri koymak için ilk , ardından çalıştırmak ekleme tür tam dizi üzerinde; eklemeli sıralamanın çalışma zamanı, her öğenin son konumundan ne kadar uzakta olduğuna bağlı olduğundan, karşılaştırma sayısı nispeten küçük kalır ve listeyi bellekte bitişik olarak saklayarak bellek hiyerarşisinden daha iyi yararlanılır.

Girdi dağılımı biliniyorsa veya tahmin edilebiliyorsa, genellikle sabit yoğunluk içeren (yalnızca sabit boyuta sahip olmak yerine) kovalar seçilebilir. Bu, eşit olarak dağıtılmış girdi olmadan bile ortalama zaman karmaşıklığına izin verir . ${\görüntüleme stili O(n)}$

Varyantlar

Genel kova sıralama

Kova sıralamanın en yaygın çeşidi, sıfır ile bazı maksimum M değerleri arasındaki n sayısal girdiden oluşan bir listede çalışır ve değer aralığını her biri M / n boyutunda n kovaya böler . Her kova eklemeli sıralama kullanılarak sıralanırsa , sıralamanın beklenen doğrusal zamanda (ortalamanın tüm olası girdiler üzerinden alındığı yerde) çalıştığı gösterilebilir. Ancak, bu sıralamanın performansı kümeleme ile düşer; birbirine yakın birçok değer oluşursa, hepsi tek bir kovaya düşecek ve yavaş yavaş sıralanacaktır. Bu performans düşüşü, girdinin öğeleri [0,1) aralığı boyunca eşit olarak dağıtan rastgele bir süreç tarafından oluşturulduğu varsayılarak orijinal kova sıralama algoritmasında önlenir .

ProxmapSıralama

Yukarıda açıklanan genel kova sıralamaya benzer şekilde, ProxmapSort , bir dizi anahtarı alt dizilere bölerek, anahtarlarda kısmi bir sıralamayı koruyan bir "harita anahtarı" işlevi kullanarak çalışır; her anahtar kendi alt dizisine eklendiğinden, bu alt diziyi sıralı tutmak için eklemeli sıralama kullanılır ve bu, ProxmapSort tamamlandığında tüm dizinin sıralı sırada olmasına neden olur. ProxmapSort, verileri yaklaşık olarak ait oldukları yere sıralı bir şekilde yerleştirmek için harita anahtarını kullanmasıyla kova sıralamalarından farklıdır ve anahtarların bir "proxmap" - bir yakınlık eşlemesi - üretir.

Histogram sıralama

Histogram sıralama veya sayma sıralama olarak bilinen başka bir kova sıralama türü, bir sayı dizisi kullanarak her bir kovaya düşecek öğelerin sayısını sayan bir başlangıç ​​geçişi ekler. Bu bilgiyi kullanarak, dizi değerleri, bir dizi değiş tokuşla yerinde bir kova dizisi halinde düzenlenebilir ve kova depolaması için ek yük bırakmaz.

Postacı sıralama

Postacının çeşit tipik özellikleri bir kümesi tarafından açıklanan elemanların bir hiyerarşik yapı, yararlanır kova tür bir varyantıdır. Bu, postanelerdeki mektup sıralama makinelerinin kullandığı algoritmadır : postalar önce yurt içi ve yurt dışı arasında sıralanır; daha sonra eyalet, il veya bölge bazında; daha sonra hedef postane tarafından; Anahtarlar birbirleriyle karşılaştırılmadığından, sıralama süresi O( cn ), burada c anahtarın boyutuna ve kova sayısına bağlıdır. Bu, "yukarıdan aşağıya" veya "önce en önemli basamak" çalışan bir sayı tabanı sıralamasına benzer .

Karışık sıralama

Karışık sıralama ilk 1/8 azaltarak başlayabilir kova tür bir varyantı olan n yinelemeli sıralar ve dizideki koyar onları, öğeleri sıralanmasını. Bu , öğelerin kalan 7/8'inin dağıtıldığı n /8 "kova" oluşturur . Her bir "kova" daha sonra sıralanır ve "kovalar" sıralanmış bir dizide birleştirilir.

Diğer sıralama algoritmaları ile karşılaştırma

Kova sıralama, sayma sıralamasının bir genellemesi olarak görülebilir ; aslında, eğer her bir kovanın boyutu 1 ise, o zaman kova sıralama, sayma sıralamasına yozlaşır. Kova sıralamanın değişken kova boyutu, M'nin farklı değerlerin sayısı olduğu O( M ) bellek yerine O( n ) belleği kullanmasına izin verir ; karşılığında, sort'un O( n + M ) en kötü durum davranışını saymaktan vazgeçer .

İki bölmeli kova sıralama, etkin bir şekilde , pivot değerinin her zaman değer aralığının orta değeri olarak seçildiği bir hızlı sıralama sürümüdür . Bu seçim tekdüze dağıtılmış girdiler için etkili olsa da, rastgele seçilen pivotlar gibi hızlı sıralamada pivotu seçmenin diğer yolları, onu girdi dağıtımında kümelenmeye karşı daha dirençli hale getirir.

N yollu mergesort algoritması da içine listesini dağıtarak başlar , n sublists ve her bir sıralama; ancak, mergesort tarafından oluşturulan alt listeler, çakışan değer aralıklarına sahiptir ve bu nedenle, kova sıralamada olduğu gibi basit birleştirme ile yeniden birleştirilemez. Bunun yerine, bir birleştirme algoritması tarafından serpiştirilmeleri gerekir. Bununla birlikte, bu ek masraf, daha basit dağılım aşaması ve her bir alt listenin aynı boyutta olmasını sağlama yeteneği ile dengelenir ve iyi bir en kötü durum zaman sınırı sağlar.

Yukarıdan aşağıya radix sıralama , hem değer aralığının hem de paket sayısının iki katı olacak şekilde sınırlandırıldığı özel bir paket sıralama durumu olarak görülebilir. Sonuç olarak, her bir kovanın boyutu da iki katıdır ve prosedür yinelemeli olarak uygulanabilir. Bu yaklaşım, dağılım aşamasını hızlandırabilir, çünkü her bir elemanın kovasını belirlemek için sadece bit temsilinin bir ön ekini incelememiz gerekir.

Referanslar

• Paul E. Siyah "Postman en Sıralama" dan Algoritmalar ve Veri Yapıları Sözlük at NIST .
• Robert Ramey '"The Postman's Sort" C Users Journal Ağustos 1992
• NIST'in Algoritmalar ve Veri Yapıları Sözlüğü: kova sıralama

Dış bağlantılar

• Ansi C için Kova Sıralama Kodu
• Demo ile Kova Sıralamasının Varyantı