Tabana göre sırala

Kaşif veya mucit	Herman Hollerith
Keşif tarihi	1887
İlgili sorun	Sıralama algoritması
Veri yapısı	Yazı tahtası

Zaman karmaşıklığı

En kötü durumda	${\ displaystyle O (w \ cdot n)}$

Uzay karmaşıklığı

En kötü durumda	${\ displaystyle O (w + N)}$

Gelen algoritmik sıralama radix veya radix sıralama için dışarı radix İngilizce, bir olan sıralama algoritması eşsiz anahtar bilgisini elemanları sipariş için kullanılır. Her anahtar bir olan karakter dizisi veya baz göre sıralama içinde sıralar bir numara lexicographic sırayla . Bu algoritmanın bir veya daha fazla kararlı sıralama algoritmasıyla birleştirilmesi gerekir .

Prensip

Algoritmanın ilkesi aşağıdaki gibidir:

Her anahtarın en az anlamlı basamağını dikkate alıyoruz.
Sabit bir sıralama algoritması ile bu sayıya göre elemanların listesini sıralıyoruz. Sıralama kararlı olduğu için aynı numaraya sahip elemanların düzeni korunur.
Bir sonraki numaraya bakarken 2. adımı tekrarlıyoruz.

Örneklerde görülebileceği gibi, bir rakam bir kartın bir değeri, bir kartın bir rengi, bir sayının ondalık yazımında bir rakam, bir bit veya bir grup bit olabilir.

Örnekler

Bir tamsayı listesini sıralama

Listeyi artan sırada sıralamak için bu algoritmayı kullanacağız: 170, 45, 75, 90, 2, 24, 802, 66 . Burada en önemsiz rakam birler rakamı, sonra onlar ve son olarak yüzlerce rakamdır. Algoritma aşağıdaki gibi çalışır.

Listeyi birimler hanesinin artan sırasına göre sıralayarak başlarız. Elde ettiğimiz: 170, 90, 2, 802, 24, 45, 75, 66 .
Elde edilen listeyi, kararlı bir sıralama kullanarak onlar basamağının artan sırasına göre sıralarız. Elde ettiğimiz: 2, 802, 24, 45, 66, 170, 75, 90 . Burada 170 , 75'ten öncedir çünkü tanım gereği aynı anahtara sahip sayıların başlangıç sırasını değiştirmeyen, burada onlar basamağı 7 olan kararlı bir sıralama kullandık.
Bu yeni listeyi, kararlı bir sıralama kullanarak yüzlerce basamaktan artan sırada sıralayarak sıralıyoruz. Daha sonra sıralı liste 2, 24, 45, 66, 75, 90, 170, 802'yi elde ederiz . 2'den 90'a kadar olan sayıların yüz basamağı yoktur, bu nedenle daha önce elde ettiğimiz konumu değiştirmeyiz.

52 kartlık bir desteyi sıralama

Bu algoritmayı , 52 kartlık bir desteyi sözlükbilimsel sıraya göre sıralamak için de kullanabiliriz .

${\ displaystyle 1 \ diamondsuit <2 \ diamondsuit <... <K \ diamondsuit <1 \ clubsuit <... <K \ clubsuit <1 \ heartsuit <... <K \ heartsuit <1 \ spadesuit <... <Q \ spadesuit <K \ spadesuit}$

için elde edilen değerler, (sayı veya kartın baş) ve sırası ile ilgili işaretler (ya da renk). ${\ displaystyle 1 <2 <3 <4 <5 <6 <7 <8 <9 <10 <J <Q <K}$ ${\ displaystyle \ diamondsuit <\ clubsuit <\ heartsuit <\ spadesuit}$

Algoritma aşağıdaki gibi çalışır.

Bir paket kart alın ve kartları kartın değerine göre düzenlemek için on üç sıra yapın. Böylece bir yığın as, ikili vb. Elde ederiz. Daha sonra bu desteleri birleştirip önce aslarla, sonra her ikisiyle ve daha sonra papazlarla birlikte bir paket elde ederiz.
Şimdi kartları renklerine göre düzenlemek için dört sıra yapıyoruz. Kartları birer birer yerleştirerek her destenin altına koyuyoruz. Bu işlem kararlıdır: Her destedeki kartlar değere göre sıralanır. Daha sonra paketleri, önce elmasları, sonra sinekleri, sonra kupa ve son olarak maçaları olacak şekilde birleştiriyoruz. Elde edilen paket, sözlüksel sıraya göre sıralanır.

Sözde kod

Genel olarak, rakamlara göre Tkodlanmış bir dizi öğe için, tabana göre sıralama algoritması şu şekildedir: $d$

fonction triParBase(T, d): Pour i allant de 1 à d Trier avec un tri stable le tableau T selon le i-ème chiffre

Bu nedenle algoritmanın çalışması, kullanılan kararlı sıralama algoritmalarında bulunur. Genellikle, i'inci rakam 1'den tümü için sıralanan sonlu sayıdaki olası değerler olduğundan , bir sıralama sayma varyantı kullanılır . Elde edildikten sonra histogram sayma sıralama verileri, bir oluşturma boyutu tablo halinde, burada , bir boyut tablosu içerir unsurları içerisinde geçiş sırasına göre sıralar gibi onların i-inci rakam olarak (bir tür kararlılık sağlar) için . $bu}$ $bu}$ ${\ displaystyle 1 \ leq i \ leq d}$ histab $bu}$ ${\ displaystyle 1 \ leq k \ leq c_ {i}}$ tab[k]his[k]TT $k$

Tarihi

Başında XX inci yüzyıl, Herman Hollerith ve EAFORD etkisini artırmıştır Tabulators oluşturarak sıralayıcı otomatik yumruk kartları radix tür ilkesine dayalı. Operatör bir sütun seçer ve ardından delikli kartları sıralayıcıya koyar. Sıralayıcı, kartları on üç kutudan birinde sakladı. İlk on iki kutu, operatör tarafından seçilen kolon üzerinde on iki olası delme pozisyonundan birine sahip olan kartlara karşılık geldi ve on üçüncü kutu, kolon üzerinde deliksiz kartlara karşılık geldi. İşlem sütunlar olduğu kadar tekrarlanarak ve her bir kutunun sırasını koruyarak, yani ilk kutunun kartlarını daha sonra ikinci kutunun kartlarını ve benzerlerini sıralayıcıya koyarak delikli kartlar sıralandı. 1923'te, tabana göre sıralama, delikli kartları sıralamak için yaygın olarak kullanıldı.

1954 yılında Harold H. Seward (en) , MIT'deki yüksek lisans tezinde ilk bilgisayar uygulamalı veritabanı sıralama algoritmasını geliştirdi. Önceki algoritmalar, farklı türler yapmak için bilinmeyen boyutlarda belirsiz sayıda liste oluşturan, tahmin edilemeyen miktarda bellek alanına ihtiyaç duydukları için bir bilgisayarda çalışmıyordu. Seward tarafından önerilen yenilik, oluşturulacak yardımcı tabloların sayısını ve boyutunu bilmek için listenin tüm öğelerine doğrusal bir geçiş yapmak ve ardından bu tablolardaki öğeleri düzenleyerek tabana göre sıralama algoritmasını uygulamaktı. Hollerith sınıflandırıcılarının on üç kutu çıktılarına karşılık gelir.

Şimdi, ikili dizeleri ve tam sayıları sıralamak için tabana göre sıralama uygulanıyor. Bu sıralama diğer algoritmalardan ortalama olarak daha hızlıdır ve bazen% 50 veya üç kat daha hızlıdır.

Karmaşıklık ve özellikler

Olası değerleri alabilen rakamlara kodlanmış bir dizi öğe boyutu için , kullanılan kararlı sıralama gerçekleştirilirse , sayma sıralamasında olduğu gibi , yürütme süresi gelir . $değil$ $d$ $k$ ${\ displaystyle O (d (n + k))}$ ${\ displaystyle O (n + k)}$

Genel olarak, eğer -inci basamak olası değerleri alabiliyorsa , zaman karmaşıklığı içerdedir . Örneğin, 52 kartlık bir destenin sıralanması durumunda, elimizde ve var . $ben$ $k_ {i}$ ${\ displaystyle O \ sol (nd + \ toplamı _ {i = 0} ^ {d} k_ {i} \ sağ)}$ ${\ displaystyle k_ {1} = 13}$ ${\ displaystyle k_ {2} = 4}$

Ne zaman sabittir ve bu , tabana göre sıralamanın zaman karmaşıklığı doğrusaldır. Bu genellikle olduğu paradigma içinde sözleşme ile programlama değerleri ve önceden ayarlanır. Örneğin , Fransız dilinde sözcükler 30 artırılarak 42'ye ( aksanlı harfler dahil olmak üzere Fransız alfabesindeki toplam harf sayısı) eşit olan sözlük sırasına göre sıralanırken bu durum söz konusudur . Bu daha bu tür hızlı yapar karşılaştırma türlü (gibi perhizden , yığın, ve birleştirme türlü olduğunu) . $d$ ${\ displaystyle k = O (n)}$ $d$ $k$ $d$ $k$ ${\ displaystyle \ Omega (n \ günlük (n))}$

Tabana göre sıralamanın en büyük dezavantajı, ek bellek alanı gerektirmesi ve giriş listesi tuşlarının her karakterinin ayrıştırılmasını gerektirmesidir, bu nedenle uzun tuşlar için çok yavaş olabilir. Bellek alanı sınırlıysa, sıralamanın yerinde kullanılması tercih edilecektir , bu da uzamsal karmaşıklığı azaltacak, ancak zamansal karmaşıklığı artıracaktır. $Biz)$

Notlar ve referanslar

(en) Knuth, Donald Ervin , Bilgisayar programlama sanatı , Addison-Wesley Pub. Co, © 1973- © 1981 ( ISBN 0-201-03809-9 , 9780201038095 ve 0201896842 , OCLC 823849 , çevrimiçi okuma ) , Bölüm 5.2.5: Dağıtıma Göre Sıralama, sayfalar 168-179
Cormen, Thomas H. ve Kocher, Georges-Louis, ( İngilizce'den çeviri ), Algorithmics: 957 alıştırma ve 158 problemli kurs , Paris, Dunod , impr . 2010, 1188 s. ( ISBN 978-2-10-054526-1 ve 2-10-054526-4 , OCLC 690855992 , çevrimiçi okuyun ) , s. 8.3 Tabana göre sırala, 182-185
(inç) Aspray, William. , Bilgisayarlardan önce hesaplama , Ames, Iowa State University Press,1990, 266 s. ( ISBN 0-8138-0047-1 ve 9780813800479 , OCLC 20690584 , çevrimiçi okuma ) , s. Bölüm 4: Delikli Kart Makinaları, sayfa 140
(in) " Ben Daha Hızlı Sıralama Algoritması yazdı " üzerine Muhtemelen Dance ,Aralık 28, 2016( 16 Kasım 2019'da erişildi )
(inç) " Radix, tamsayı dizileri için hızlı sıralamadan çok daha mı hızlıdır? » , On erik.gorset.no (erişim tarihi : 16 Kasım 2019 )
(in) " Fonksiyon şablon integer_sort - 1.62.0 " üzerine www.boost.org (erişilen 2019 16 Kasım )

Dış bağlantı

Tabana (en) göre sıralamanın gösterimi ve JavaScript ile karşılaştırılması