Radix sıralama - Radix sort

Radix sıralama
Sınıf sıralama algoritması
Veri yapısı Dizi
En kötü durum performansı , burada n anahtar sayısıdır ve w anahtar uzunluğudur.
En kötü durum alanı karmaşıklığı

Gelen bilgisayar bilimleri , basamağa göre sıralama olmayan bir olduğunu karşılaştırmalı sıralama algoritması . Bu oluşturup karşılaştırma önler dağıtarak onların göre kova içine unsurları radix . Birden fazla anlamlı basamağa sahip öğeler için , bu kovalama işlemi, tüm basamaklar dikkate alınana kadar önceki adımın sırası korunurken her basamak için tekrarlanır. Bu nedenle radix sıralama , kova sıralama ve dijital sıralama olarak da adlandırılmıştır .

Radix sıralama, tamsayılar, kelimeler, delikli kartlar, oyun kartları veya posta gibi sözlükbilimsel olarak sıralanabilen verilere uygulanabilir .

Tarih

Radix sıralama, 1887'ye kadar, Herman Hollerith'in tablolama makineleri üzerindeki çalışmasına kadar uzanır . Radix sıralama algoritmaları , 1923 gibi erken bir tarihte delikli kartları sıralamanın bir yolu olarak yaygın olarak kullanılmaya başlandı.

Belleği verimli kullanan ilk bilgisayar algoritması 1954'te MIT'de Harold H. Seward tarafından geliştirildi . Bilinmeyen boyuttaki kovaların değişken tahsisi için algılanan ihtiyaç nedeniyle, bilgisayarlı sayı tabanı sıralamaları daha önce pratik olmadığı için reddedilmişti. Seward'ın yeniliği, gerekli kova boyutlarını ve ofsetleri önceden belirlemek için doğrusal bir tarama kullanmaktı, böylece yardımcı belleğin tek bir statik tahsisine izin verildi. Doğrusal tarama, Seward'ın diğer algoritması sayma sıralama ile yakından ilişkilidir .

Modern çağda, sayı tabanı türleri en yaygın olarak ikili diziler ve tamsayılar koleksiyonlarına uygulanır . Bazı kıyaslamalarda diğer genel amaçlı sıralama algoritmalarından daha hızlı olduğu, bazen %50 ila üç kat daha hızlı olduğu gösterilmiştir.

Bir sıralayıcı IBM kart geniş setinde bir sayı tabanı tür performans bekleşirdik . Kartlar, operatörün çenesinin altındaki bir hazneye beslenir ve kartlardaki bir sütuna delinmiş verilere dayalı olarak makinenin 13 çıktı sepetinden birine sıralanır. Giriş haznesinin yanındaki krank, sıralama ilerledikçe okuma kafasını bir sonraki sütuna taşımak için kullanılır. Arkadaki raf, önceki sıralama geçişinden kartları tutar.

Rakam sırası

Radix sıralamaları, en önemli basamaktan (MSD) veya en az anlamlı basamaktan (LSD) başlamak için uygulanabilir . Örneğin, 1234 ile 1 (MSD) veya 4 (LSD) ile başlanabilir.

LSD sayı tabanı sıralamaları tipik olarak aşağıdaki sıralama düzenini kullanır: kısa anahtarlar daha uzun anahtarlardan önce gelir ve ardından aynı uzunluktaki anahtarlar sözlükbilimsel olarak sıralanır . Bu, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] dizisi gibi tamsayı gösterimlerinin normal sırası ile çakışır . LSD türleri genellikle kararlı türlerdir .

MSD sayı tabanı sıralamaları, dizileri veya sabit uzunluklu tamsayı gösterimlerini sıralamak için en uygundur. [b, c, e, d, f, g, ba] gibi bir dizi [b, ba, c, d, e, f, g] olarak sıralanır . Lexicographic sipariş 10 tabanına sıralama değişken uzunluklu tamsayılar kullanılırsa, o zaman 1 ile 10 arasında sayılar olarak verilir olacaktır [1, 10, 2, 3, 4, 5, 6, 7, 8, 9] , gibi daha kısa tuşlar, daha kısa tuşları en uzun tuş kadar uzun yapmak için sola yaslanmış ve sağda boş karakterlerle doldurulmuştur. Yinelenen anahtarların orijinal sıralamasının her zaman korunması gerekiyorsa, MSD sıralamaları mutlaka kararlı değildir.

Geçiş sırası dışında, MSD ve LSD sıralamaları, değişken uzunluk girdisini işlemede farklılık gösterir. LSD sıralamaları, uzunluğa göre gruplandırabilir, her grubu tabanda sıralayabilir, ardından grupları boyut sırasına göre birleştirebilir. MSD sıralamaları, tüm kısa anahtarları etkin bir şekilde en büyük anahtarın boyutuna 'genişletmeli' ve bunları buna göre sıralamalıdır; bu, LSD'nin gerektirdiği gruplandırmadan daha karmaşık olabilir.

Ancak, MSD türleri alt bölümlere ayırmaya ve özyinelemeye daha uygundur. Bir MSD adımı tarafından oluşturulan her bir grup, bir önceki adımda oluşturulan diğer paketlere atıfta bulunmaksızın, bir sonraki en önemli basamak kullanılarak taban olarak sıralanabilir. Son basamağa ulaşıldığında, sıralamayı tamamlamak için gereken tek şey kovaları birleştirmek.

Örnekler

En az anlamlı basamak

Giriş listesi (taban 10):

[170, 45, 75, 90, 2, 802, 2, 66]

En sağdaki (son) basamaktan başlayarak sayıları o basamağa göre sıralayın:

[{17 0 , 9 0 }, { 2 , 80 2 , 2 }, {4 5 , 7 5 }, {6 6 }]

Sonraki sol basamağa göre sıralama:

[{ 0 2, 8 0 2, 0 2}, { 4 5}, { 6 6}, {1 7 0, 7 5}, { 9 0}]
802'nin aralarındaki konumunu koruması için iki 2'nin başına bir örtük 0 rakamının eklendiğine dikkat edin.

Ve son olarak en soldaki rakamla:

[{ 0 0 2, 0 0 2, 0 45, 0 66, 0 75, 0 90}, { 1 70}, { 8 02}]
Tüm 1 veya 2 basamaklı sayıların başına 0 geldiğine dikkat edin .

Her bir öğe, diğer herhangi bir öğeyle karşılaştırılmadan kendi kovasına yerleştirilebildiğinden, her adım, veriler üzerinden yalnızca tek bir geçiş gerektirir.

Bazı sayı tabanı sıralama uygulamaları, anahtarları bu kovalara taşımadan önce her bir kovaya ait olan anahtarların sayısını sayarak kovalar için alan ayırır. Her basamağın oluşma sayısı bir dizide saklanır .

Sayıları kullanarak paket sınırlarını önceden belirlemek her zaman mümkün olsa da, bazı uygulamalar bunun yerine dinamik bellek ayırmayı kullanmayı tercih eder.

En anlamlı basamak, ileri özyinelemeli

Giriş listesi, başında sıfır olan sabit genişlikli sayısal dizeler:

[170, 045, 075, 025, 002, 024, 802, 066]

Kovaları gösteren parantezlerle birlikte ilk hane:

[{ 0 45, 0 75, 0 25, 0 02, 0 24, 0 66}, { 1 70}, { 8 02}]
170 ve 802'nin zaten tamamlandığına dikkat edin, çünkü kovalarında kalanların hepsi bunlardır, bu nedenle daha fazla özyinelemeye gerek yoktur.

Sonraki rakam:

[{ {0 0 2}, {0 2 5, 0 2 4}, {0 4 5}, {0 6 6}, {0 7 5} }, 170, 802]

Son rakam:

[ 002, { {02 4 }, {02 5 } }, 045, 066, 075 , 170, 802]

Geriye kalan tek şey birleştirme:

[002, 024, 025, 045, 066, 075, 170, 802]

Karmaşıklık ve performans

Radix sıralama, O ( nw ) zamanında çalışır; burada n , anahtar sayısı ve w anahtar uzunluğudur. LSD varyantları, yukarıda tartışıldığı gibi değişken uzunluklu anahtarları gruplara ayırırken w için 'ortalama anahtar uzunluğu' için bir alt sınır elde edebilir .

Optimize edilmiş sayı tabanı sıralamaları, kendilerine uygun bir alanda çalışırken çok hızlı olabilir. Sözlükbilimsel verilerle sınırlıdırlar, ancak birçok pratik uygulama için bu bir sınırlama değildir. Büyük anahtar boyutları, indüklenen geçiş sayısı darboğaz olduğunda LSD uygulamalarını engelleyebilir.

Özel varyantlar

Yerinde MSD sayı tabanı sıralama uygulamaları

İkili hızlı sıralama olarak da adlandırılan ikili MSD taban sıralaması, giriş dizisini iki bölmeye bölerek yerinde uygulanabilir - 0s kutusu ve 1s kutusu. 0s kutusu dizinin başından büyütülürken, 1s kutusu dizinin sonundan büyütülür. 0s bin sınırı, ilk dizi öğesinden önce yerleştirilir. 1s bin sınırı, son dizi öğesinden sonra yerleştirilir. İlk dizi öğesinin en önemli biti incelenir. Bu bit 1 ise, o zaman ilk eleman 1s bin sınırının (dizinin son elemanı) önündeki elemanla değiştirilir ve 1s kutusu, 1s sınır dizi indeksi azaltılarak bir eleman tarafından büyütülür. Bu bit 0 ise, ilk eleman mevcut konumunda kalır ve 0s kutusu bir eleman tarafından büyütülür. İncelenen sonraki dizi öğesi, 0s bin sınırının önündekidir (yani, 0s bin veya 1s binde olmayan ilk öğe). Bu işlem 0s bin ve 1s bin birbirine ulaşana kadar devam eder. 0s kutusu ve 1s kutusu daha sonra her dizi öğesinin bir sonraki bitine göre özyinelemeli olarak sıralanır. Özyinelemeli işleme, sıralama için en az anlamlı bit kullanılana kadar devam eder. İşaretli tam sayıların işlenmesi, en anlamlı bitin zıt anlamda ele alınmasını, ardından bitlerin geri kalanının işaretsiz olarak işlenmesini gerektirir.

Yerinde MSD ikili tabanlı sıralama, daha büyük sayı tabanına genişletilebilir ve yerinde özelliği korur. Sayma sıralaması , her bir kutunun boyutunu ve başlangıç ​​indeksini belirlemek için kullanılır. Değiştirme, geçerli öğeyi bölmesine yerleştirmek ve ardından bölme sınırını genişletmek için kullanılır. Dizi öğeleri taranırken, bölmeler atlanır ve tüm dizi işlenene ve tüm öğeler kendi bölmelerine gelene kadar yalnızca bölmeler arasındaki öğeler işlenir. Kutu sayısı, kullanılan sayı tabanı ile aynıdır - örneğin, 16-tabanlı için 16 kutu. Her geçiş, en önemli basamaktan başlayarak tek bir basamağa (örneğin, 16-radix durumunda basamak başına 4-bit) dayanır . Her bir bölme daha sonra, tüm basamaklar sıralama için kullanılana kadar bir sonraki basamak kullanılarak özyinelemeli olarak işlenir.

Yukarıdaki paragraflarda tartışılan yerinde ikili tabanlı sıralama veya n-bit tabanlı sıralama, kararlı algoritmalar değildir .

Kararlı MSD sayı tabanı sıralama uygulamaları

MSD radix sort kararlı bir algoritma olarak uygulanabilir, ancak giriş dizisiyle aynı boyutta bir bellek arabelleğinin kullanılmasını gerektirir. Bu ekstra bellek, giriş arabelleğinin ilk dizi öğesinden sonuncuya kadar taranmasına ve dizi öğelerinin aynı sırayla hedef bölmelere taşınmasına olanak tanır. Böylece, eşit elemanlar, giriş dizisindekilerle aynı sırada bellek arabelleğine yerleştirilecektir. MSD tabanlı algoritma, birinci özyineleme düzeyinde çıktı olarak fazladan bellek arabelleğini kullanır, ancak çıktı sonucunu giriş arabelleğine geri kopyalama ek yükünü önlemek için bir sonraki özyineleme düzeyinde girdi ve çıktıyı değiştirir. Bölmelerin her biri, yerinde MSD sayı tabanı sıralaması için yapıldığı gibi yinelemeli olarak işlenir. Son basamağa göre sıralama tamamlandıktan sonra, orijinal giriş dizisi olup olmadığını görmek için çıktı arabelleği kontrol edilir ve değilse, tek bir kopya gerçekleştirilir. Rakam boyutu, anahtar boyutunun basamak boyutuna bölümü çift sayı olacak şekilde seçilirse, sondaki kopyadan kaçınılır.

Hibrit yaklaşımlar

Sayı tabanı, sıralama gibi iki geçişli yöntem çeşit sayma yineleme her düzeyde ilk geçiş sırasında kullanılan, büyük bir sabite sahiptir. Bu nedenle, kutular küçüldüğünde, eklemeli sıralama gibi diğer sıralama algoritmaları kullanılmalıdır . Eklemeli sıralamanın iyi bir uygulaması, küçük diziler için hızlıdır, sabittir, yerindedir ve sayı tabanı sıralamasını önemli ölçüde hızlandırabilir.

Paralel hesaplama uygulaması

Bu özyinelemeli sıralama algoritmasının, her bir kutu bağımsız olarak sıralanabileceğinden, paralel hesaplama için özel bir uygulaması olduğunu unutmayın . Bu durumda, her bin bir sonraki kullanılabilir işlemciye geçirilir. Başlangıçta tek bir işlemci kullanılacaktır (en önemli basamak). İkinci veya üçüncü basamakta, mevcut tüm işlemciler büyük olasılıkla devreye girer. İdeal olarak, her alt bölüm tam olarak sıralandığından, giderek daha az işlemci kullanılacaktır. En kötü durumda, tüm anahtarlar birbiriyle aynı veya neredeyse aynı olacaktır, bunun sonucunda anahtarları sıralamak için paralel hesaplama kullanmanın çok az veya hiç avantajı olmayacaktır.

Özyinelemenin en üst seviyesinde, paralellik fırsatı , algoritmanın sayma sıralama kısmındadır. Sayma oldukça paraleldir, parallel_reduce modeline uygundur ve işi bellek bant genişliği sınırına ulaşana kadar birden çok çekirdeğe böler. Algoritmanın bu kısmı veriden bağımsız paralelliğe sahiptir. Bununla birlikte, her bir bölmeyi sonraki özyineleme seviyelerinde işlemek verilere bağlıdır. Örneğin, tüm anahtarlar aynı değerde olsaydı, içinde herhangi bir öğe bulunan yalnızca tek bir çöp kutusu olurdu ve hiçbir paralellik mevcut olmazdı. Rastgele girişler için tüm kutular eşit olarak doldurulacak ve büyük miktarda paralellik fırsatı mevcut olacaktır.

Not olduğu hızlı örneğin algoritmaları sıralama paralel uygun karmaşıklığı O (log ( n )) ç Macar ve olanlardır Richard Cole ve Besleyici sitesindeki bitonic birleştirme sıralaması O algoritmik karmaşıklığı (log 2 ( n )) bunların tümü, bir CREW- PRAM üzerinde sayı tabanı sıralaması için daha düşük bir algoritmik zaman karmaşıklığına sahiptir . Bilinen en hızlı PRAM türleri, 1991 yılında David Powers tarafından, örtük olarak bölümleme gerçekleştirerek n işlemcili bir CRCW-PRAM üzerinde O(log(n)) zamanında çalışabilen paralelleştirilmiş bir hızlı sıralama ve ayrıca aşağıdakileri kullanarak çalışan bir radixsort ile tanımlandı. O( k ) içindeki aynı numara , burada k maksimum anahtar uzunluğudur. Bununla birlikte, ne PRAM mimarisi ne de tek bir sıralı işlemci, döngü başına O(log( n ) olarak artan sabit yayma kapısı gecikmelerinin sayısı olmadan ölçeklenecek bir şekilde oluşturulamaz , böylece aslında boru hatlı bir sürüm olur. Batcher'ın bitonik birleştirme sıralaması ve O(log( n )) PRAM türlerinin tümü , saat döngüleri açısından O(log 2 ( n ))'dir, Powers, Batcher'ın Geçit gecikmeleri açısından Paralel hızlı sıralamasından daha düşük sabite sahip olacağını kabul eder ve O(nlog 2 ( n )) anahtar uzunluğundan bağımsız bir sıralama ağı için sayı tabanı sıralama veya Cole'un birleştirme sıralama .

Trie tabanlı sayı tabanı sıralama

Radix sıralama , giriş kümesinden bir trie (veya radix tree ) oluşturarak ve bir ön sipariş geçişi yaparak da gerçekleştirilebilir . Bu, yığın sıralaması ve yığın veri yapısı arasındaki ilişkiye benzer . Bu, belirli veri türleri için faydalı olabilir, bkz. burstsort .

Ayrıca bakınız

Referanslar

Dış bağlantılar