Bilgisayar bilimlerinde, tamsayı dizilerini artan ya da azalan bir şekilde sıralayabilecek birçok metot vardır. Radix Sort, sayıları basamaklarının üzerinde işlem yaparak sıralayan doğrusal sıralama algoritmalarından biridir. Radix Sort algoritması, 1887 yılında Hollerith’in patentini aldığı “tabulating machine” için kullandığı yönteme dayalıdır. Esasta, 2 tabanına göre yazılmış sayıları sıralayan hızlı bir algoritmadır. Sayma sayıları, adlar ya da tarihler gibi karakter dizilerini göstermek için de kullanılabildiğinden basamağa göre sıralama algoritması yalnızca sayma sayılarını sıralamak için kullanılan bir algoritma değildir. Radix Sort, hane sıralaması veya kök sıralaması isimleri ile de anılmaktadır.
Çoğu bilgisayar veri saklamak için ikilik tabandaki sayıların elektronikteki gösterim biçimlerini kullandığından sayma sayılarının basamaklarını ikilik tabandaki sayılardan oluşan öbekler biçiminde göstermek daha kolaydır. Basamağa göre sıralama algoritması, en anlamsız basamağa göre sıralama ve en anlamlı basamağa göre sıralama olarak ikiye ayrılır. En anlamsız basamağa göre sıralama algoritması sayıları en anlamsız (en küçük, en sağdaki) basamaktan başlayıp en anlamlı basamağa doğru yürüyerek sıralarken en anlamlı basamağa göre sıralama algortiması bunun tam tersini uygular.
Sıralama algoritmaları tarafından işlenen ve kendi sayı değerlerini gösterebildiği gibi başka tür verilerle de eşleştirilebilen sayma sayılarına çoğu zaman anahtardenir. En anlamsız basamağa göre sıralamada kısa anahtarlar uzunlardan önce gelirken aynı uzunluktaki anahtarlar sözlükteki sıralarına göre sıralanırlar. Bu sıralama biçimi sayma sayılarının kendi değerlerine göre sıralandıklarında oluşan sırayla aynı sırayı oluşturur. Örneğin 1'den 10'a kadar olan sayılar sıralandığında ortaya 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 dizisi çıkacaktır.
En anlamlı basamağa göre sıralama sözcükler ya da aynı uzunluktaki sayılar gibi dizileri sıralamak için uygun olan sözlükteki sıraya göre sıralar. Örneğin; "b, c, d, e, f, g, h, i, j, ba" dizisi sözlük sırasına göre "b, ba, c, d, e, f, g, h, i, j" olarak sıralanacaktır. Eğer sözlük sırası değişken uzunluktaki sayılarda uygulanırsa sayılar değerlerinin gerektirdiği konumlara konulmazlar. Örneğin; 1'den 10'a kadar olan sayılar sıralandığında, algoritma kısa olan sayıların sonuna boş karakter koyarak bütün anahtarları en uzun anahtarla aynı boyuta getireceğinden sonuç 1, 10, 2, 3, 4, 5, 6, 7, 8, 9 olacaktır.
Örnek olarak; 57, 43, 24, 213, 44, 102, 70, 37, 111, 23 sayıları Radix Sort algoritması ile sıralanabilir.
- İlk geçişte sayılar birler basamağına göre artan yönde sıralanır. Birler hanesinde aynı değeri alan 43, 213, 23 gibi sayılar, başlangıç dizisindeki veriliş sırasıyla yazılırlar.70, 111, 102, 43, 213, 23, 24, 44, 57, 37
- İkinci geçişte, ilk geçişte elde edilen dizi onlar basamağındaki değerlerine göre sıralanır.102, 111, 213, 23, 24, 37, 43, 44, 57, 70
- Üçüncü geçişte, ikinci geçişte elde edilen dizi yüzler basamağındaki değerlerine göre sıralanır.23, 24, 37, 43, 44, 57, 70, 102, 111, 213
Görüldüğü gibi, en soldaki basamağa göre geçiş bitince, sayılar sıralanmış olur. Bilgisayar, sayıları bellekte 2 tabanına göre tuttuğu için, Radix Sort algoritması 2 tabanında yazıldığında, 10 tabanından 2 tabanına dönüşüm için zaman harcanmayacağından algoritma daha hızlı çalışır. Yukarıda yapılan sıralama işleminde her aşamada bütün sayı kümesi üzerinden bir kere geçilmesi gerekmektedir. Yani n sayılık bir küme için her aşama n adım gerektirir. Örneğin; 10'luk sayı tabanında her sayıdan birer tane bulunması halinde her hane için 10 ihtimal bulunur. Bu her ihtimalin ayrı bir hafıza bölümünde tutulması durumunda sıralama işlemi (en büyük hane sayısı) * n olmaktadır.
Algoritmanın C# Programlama Diliyle Gerçeklenmesi
Aşağıdaki "radixSort" metodu yardımıyla, oluşturulan rastgele sayıların birler basamağından başlanarak basamaklarına ulaşılır ve bu değerler "digits[]" dizisinde tutulur.
public class RadixSort
{
public static int[] radixSort(int[] A, int d)
{
bool Empty = true;
KVEntry[] digits = new KVEntry[A.Length];//array that holds the digits;
int[] SortedArray = new int[A.Length];//Hold the sorted array
for (int i = 0; i < A.Length; i++)
{
digits[i] = new KVEntry();
digits[i].Key = i;
digits[i].Value = (A[i] / d) % 10;
if (A[i] / d != 0)
Empty = false;
}
if (Empty)
return A;
KVEntry[] SortedDigits = CountingSort.countingSort(digits,10);
for (int i = 0; i < SortedArray.Length; i++)
SortedArray[i] = A[SortedDigits[i].Key];
return radixSort(SortedArray, d * 10);
}
}
"countingSort" metodu yardımıyla da, "radixSort" metodu ile birler basamağından başlanarak elde edilen basamaklardaki sayı değerlerine göre sıralama yapılır.
public class KVEntry
{
public int Key;
public int Value;
}
public class CountingSort
{
public static KVEntry[] countingSort(KVEntry[] A, int k)
{
int[] C = new int[k];
KVEntry[] B = new KVEntry[A.Length];
int i, j;
for (i = 0; i < k; i++)
{
C[i] = 0;
}
for (j = 0; j < A.Length; j++)
{
C[A[j].Value] = C[A[j].Value] + 1;
}
for (i = 1; i < k; i++)
{
C[i] = C[i] + C[i - 1];
}
for (j = A.Length - 1; j >= 0; j--)
{
int value = A[j].Value;
int index = C[value];
C[value]--;
B[index - 1] = new KVEntry();
B[index - 1].Key = j;
B[index - 1].Value = value;
}
return B;
}
}
Program çalıştırıldığında sıralanması istenen rastgele sayı miktarı girilir ve oluşturulan rastgele sayıların sıralanması sırasında geçen süre ekrena yazdırılır.
protected void Button1_Click(object sender, EventArgs e)
{
Label1.Text = "";
int sayı_adeti = Convert.ToInt32(TextBox1.Text);
int[] A = new int[sayı_adeti];
Random rand = new Random();
Stopwatch stopwatch = new Stopwatch();
for (int i = 0; i < sayı_adeti; i++)
{
A[i] = rand.Next(0, 100000);
}
stopwatch.Start();
A = RadixSort.radixSort(A, 1);
stopwatch.Stop();
TimeSpan time = stopwatch.Elapsed;
Response.Write("\nGeçen süre:\t" + time.ToString());
if (sayı_adeti <= 100)
{
for (int i = 0; i < sayı_adeti; i++)
{
Label1.Text += A[i] + "\t";
}
}
}
Program çalıştırıldıktan sonra ekran görüntüsü şekildeki gibi olur.
Verimlilik
Diğer sıralama algoritmaları ile karşılaştırıldığında radix tür verimlilik konu biraz zor ve yanlış anlaşılmalar oldukça çok tabidir. Radix sort eşit verimli daha az verimli ya da en iyi karşılaştırma tabanlı algoritmalar daha verimli olup olmadığı yapılan varsayımların ayrıntıları bağlıdır. Radix sıralama karmaşıklığı
O ( wn ) için
n tam sayılardır anahtarları kelime boyutu
w . Bazen
w (yeterince büyük sıralama daha iyi tabanını yapacak, hangi sabit olarak sunulmuştur
n tüm gerçekleştirmek en iyi karşılaştırma tabanlı sıralama algoritmaları, yerine)
O ( n log n ) sıralamak için karşılaştırmalar
ntuşlarına basın. Ancak, genel olarak
w sabit kabul edilemez: hepsi değilse
n tuşları farklıdır, o
w azından zorundadır
log nbir için rasgele erişim makinasında en iyi bir zaman karmaşıklığı veren bellekte saklayabilirsiniz edebilmek için
O ( n log n ). Bu (tuşlar daha uzun iseniz ve kötü iyi karşılaştırma tabanlı türlü olarak radix sort en eşit verimli hale getirmek gibi görünüyor
günlük n ).
Karşı argüman karşılaştırma tabanlı algoritmalar karşılaştırmalar sayısı değil, gerçek zaman karmaşıklığı ölçülmektedir olduğunu. Bazı varsayımlar altında karşılaştırmalar başkaları altında onlar değil, ortalama sabit zaman olacak. Tuşları böylece yarım durumlarda ilk bit farklılık ve kalan yarısının yarısında ikinci bit farklılık gibi rastgele üretilen anahtarların karşılaştırmalar iki bit ortalama sonuçlanan, ortalama sabit zaman alır karşılaştırılabilir gerekir. Bir sıralama algoritması ilk karşılaştırmalar Sağlama, rasgelelik koşulu yapılmış, ancak sıralama karşılaştırıldığında tuşları ilerledikçe açıkça rastgele seçilmiş artık değil. Örneğin, bir aşağıdan yukarıya birleştirme tür düşünün. İlk geçiş rastgele tuşları çiftleri karşılaştırmak, ancak son pas sıralama sırayla çok yakın olan anahtarları karşılaştırmak olacaktır.
belirleyici bir faktör tuşları nasıl dağıtıldığını olduğunu. radix sort en iyi durumda onlar ardışık bit desenleri olarak kabul edilmesidir. Bu yine de farklı olduğunu varsayarsak, bunlar olabilir gibi tuşları kısa yapacaktır. Bu Radix sıralama yaparÇ ( n log n ) , ancak karşılaştırmalar bu varsayımı altında, sabit bir zaman olmayacak gibi karşılaştırma bazlı türlü verimli olmayacaktır. Yerine anahtarları uzunluğu bit desenleri olduğunu kabul edersek k günlüğü n sabit için k > 1 ve taban-iki logaritma ve onlar tekdüze rasgele olduğunu, daha sonra radix sort hala olacaktır Ç ( n log n ) , ama çok olacak karşılaştırma tabanlı türlü "ekstra" uzunluk karşılaştırmalar ortalama zaman sabiti olduğu sıralanmış sonucu ardışık bile tuşları yeterince farklılık yapar. Tuşları daha uzun ise O (log n ) , ama rastgele, o zaman radix sort aşağı olacaktır. Yanı sıra yapılan ve çoğu doğru karşılaştırma yapmak için dikkatli bir çalışma gerektiren bir çok diğer varsayımlar vardır.
En az önemli basamak radix türlü
Bir az önemli basamak (LSD) radix sort bir hızlı istikrarlı sıralam
algoritması tamsayı temsil sırayla anahtarlarını sıralamak için kullanılabilir. Tuşları olabilir dize verilen 'tabanda' karakter veya sayısal basamak. tuşların işlem başlar en az önemli
basamak (yani en sağdaki basamak) ve ilerler en önemli
basamağın (yani en soldaki rakam). basamaklı bir tarafından işlendikleri sekans LSD radix tür basamaklı bir yan işleme edildiği dizisinin tersi olan em yüksek
değer basamağı (MSD) radix tür.
Bir LSD radix sort faaliyet O ( nk nerede,) zamanında n anahtarlarının sayısı ve k ortalama anahtar uzunluğudur. Değişken uzunluklu şifreler ifa Bu tür işleme önlemek için, kısa mesafede en uzun birlikte, aynı uzunluğa sahip olan anahtarların her gruplama ve ayrı ayrı her bir uzunluk için anahtarların her biri grup bir LSD radix tür bir performans elde edilebilir Her sıralama geçişte tuşların tüm liste.
Bir radix sıralama algoritması aslında sıralamak için kullanılan delikli kartlar geçişinde çeşitli geçiş içinde. Bir bilgisayar algoritması 1954 yılında radix sıralama için icat edilmiştir Mit tarafından Harold H.
Seward . Hız gerektiren birçok büyük uygulamalarda, bilgisayar radix sort (yavaş) karşılaştırma türlü bir gelişmedir.
Karşılastırmalı sıralar daha iyi yapabilirim O daha ( n · log n yürütme zamanı) ama lexicographic birden fazla karmaşık orderings göre sıralamak edememek esneklik sunar; Bununla birlikte, bu özellik birçok pratik uygulamalarda az önem taşımaktadır.
Tanım
Her anahtar mecazi sağdaki rakam değerine karşılık gelen kovalar bir seviye içine düştü ilkidir. Tuşları kovanın içine düştü gibi her kova tuşları orijinal düzenini korur. Kova ve en sağdaki basamak ile temsil edilebilir değerler arasında bire-bir uygunluk yoktur. Işlemek için daha fazla basamak vardır kadar Sonra, süreç bir sonraki komşu daha önemli basamak ile tekrarlar. Diğer bir deyişle:
- En az önemli rakam (ya da bit grup, hem varlık örnekleri alın tabandaki her tuşun).
- Grup tuşları o rakam dayanarak, ama başka türlü tuşları orijinal düzeni sağlamak. (Bu tür LSD tabanını bir ne yapar istikrarlı tür .)
- Her daha önemli rakam ile gruplama işlemi tekrarlayın.
2. adımda sıralama genellikle kullanılarak yapılır kova sıralama veya sayma tür genellikle rakamlardan sadece az sayıda var çünkü bu durumda verimli.
Bir örnek
Özgün, sıralanmamış liste:
- 170, 45, 75, 90, 802, 2, 24, 66
En az önemli basamak (1s yeri) göre sıralama verir:
- 17 0 , 9 0 , 80 2 , 2 , 2 4 , 4 5 , 7 5 , 6 6
- 802 çift 170 & 90 ve 45 & 75 için benzer şekilde orijinal listesinde 2 önce meydana, çünkü biz 2 önce 802 tutmak dikkat edin.
Bir sonraki haneli (10s yer) göre sıralama verir:
- 8 0 2, 2, 2 4, 4 5, 6 6, 1 7 0, 7 5, 9 0
- 802 olarak 2 önceki listede 2 önce gelir önce 802 tekrar geliyor dikkat edin.
En önemli haneli (100s yer) göre sıralama verir:
- 2, 24, 45, 66, 75, 90, 1 70, 8 02
Her madde diğer öğeleri ile karşılaştırıldığında gerek kalmadan onun doğru kovaya yerleştirilebilir çünkü yukarıdaki adımların her veri üzerinde sadece tek bir geçiş gerektirir fark etmek önemlidir.
Bazı radix sort uygulamaları ilk önce o kova içine anahtarları geçmeden önce her kova ait tuş sayısını sayarak kova için yer tahsis eder. Her rakam oluşur sayısı bir depolanır diziye . Farklı bir şekilde bakıldığında şifreler önceki listesini göz önünde bulundurun:
- 170, 045, 075, 090, 002, 024, 802, 066
İlk sayım geçiş kova boyutlarda bir dizi üreten, her tuşun en önemli basamak başlar:
- 2 (0 basamak için kova boyutu: 17 0 , 09 0 )
- 2 (2 basamak için kova boyutu: 00 ile 2 , 80 2 )
- 1 (4 basamak için kova boyutu: 02 4 )
- 2 (5 basamak için kova boyutu: 04 5 , 07 5 )
- 1 (6 basamak için kova boyutu: 06 6 )
Her tuşun sonraki daha önemli rakam üzerinde ikinci bir sayım geçiş kova boyutlarda bir dizi üretecek:
- 2 (0 basamak için kova boyutu: 0 0 2 8 0 2)
- 1 (2 basamak için kova boyutu: 0 2 4)
- 1 (4 basamak için kova boyutu: 0 4 5)
- 1 (6 basamak için kova boyutu: 0 6 6)
- 2 (7 basamak için kova boyutu: 1 7 0 0 7 5)
- 1 (9 basamak için kova boyutu: 0 9 0)
Her tuşun en önemli basamağının üzerine üçüncü ve son sayım geçiş kova boyutlarda bir dizi üretecek:
- 6. (0 basamak için kova boyutu: 0 02 0 24 0 45 0 66 0 75 0 90)
- 1 (1 basamak için kova boyutu: 1 70)
- 1 (8 basamak için kova boyutu: 8 02)
En az bir LSD radix sort uygulanması şimdi her rakam tek sayma geçişte tüm sütunlar için her sütunda oluşur sayısını sayar. Diğer LSD radix sort uygulamaları alan gerektiğinde dinamik olarak kovalar için yer tahsis eder.
İteratif sürümünü kullanıyorsanız kuyruklar
LSD radix tür basit versiyonu kullanılarak elde edilebilir sıraları kovalar olarak. Aşağıdaki işlem uzun anahtarın uzunluğuna eşit kez tekrarlanır:
- tamsayılar sağdan sola doğru kendi basamak dayalı on ayrı kuyruklar bir diziye kuyruğa edilir.Bilgisayarlar genellikle tamsayılar dahili olarak sabit uzunlukta ikili basamak temsil etmektedir.Burada, biz sabit uzunluklu ondalık basamak ile benzer bir şey yapacak.Yani, bir önceki örnekte numaralarını kullanarak, 1. pass kuyruklar olurdu:
- 0: 17 0 , 09 0
- 1: yok
- 2: 00 2 , 80 2
- 3: yok
- 4: 02 4
- 5: 04 5 , 07 5
- 6: 06 6
- 7-9: yok
- kuyruklar artan sırada, arka tamsayılar bir diziye dequeued edilir.Aynı numaralarını kullanarak, dizi, ilk geçişten sonra bu gibi görünecektir:
- 170, 090, 002, 802, 024, 045, 075, 066
- İkinci geçmek için:
- Kuyruklar:
- 0: 0 0 2 8 0 2
- 1: yok
- 2: 0 2 4
- 3: yok
- 4: 0 4 5
- 5: yok
- 6: 0 6 6
- 7: 1 7 0 0 7 5
- 8: yok
- 9: 0 9 0
- Dizi:
- 002, 802, 024, 045, 066, 170, 075, 090
(sadece 802 ve 170 sıra dışı olan bu noktada unutmayın)
- Üçüncü geçmek için:
- Kuyruklar:
- 0: 0 02, 0 24, 0 45, 0 66, 0 75, 0 90
- 1: 1 70
- 2-7: yok
- 8: 8 02
- 9: yok
- Dizi:
- 002, 024, 045, 066, 075, 090, 170, 802 (sıralı)
Bu en verimli radix sıralama algoritması olmayabilir iken, nispeten basit, ve hala oldukça etkilidir. Tüm 100M üzerinde testler veya daha az rastgele 64 bit tamsayı sırasında, qsort algoritması hızlı davranır. C Aşağıdaki kod Cormen ark sağlanan sayım sıralama algoritması dayanmaktadır.,
[ 3 ] bellek ayırma konusunda bazı iyileştirmeler ile.
En önemli basamak radix türlü
Bir en önemli basamak (MSD) radix sort anahtarları sıralamak için kullanılabilecek lexicographic sırayla . Bir az önemli basamak (LSD) radix sıralama aksine, en önemli basamak radix sort mutlaka yinelenen tuşları orjinal düzeni korumak değil . Bir MSD radix sort tuşları işleme başlar en önemli basamak için, en soldaki rakam en az önemli basamak , en sağdaki rakam. Bu sekans bunun tam tersidir en az önemli basamak (LSD) radix türlü. Bir MSD radix sort işleme anahtarının benzersiz bir önek ulaştığı bir anahtarın konumunu yeniden düzenleme durdurur. Bazı MSD Radix türlü hangi tuşların grubuna kovalar bir seviye kullanın ve Diğer MSD Radix sıralar bir formu kovalar, çoklu düzeyde kullanmak tray veya tray bir yol. Bir postacının sıralama / posta sıralama MSD radix tür bir türüdür.
Özyineleme
Bir yinelemeli şöyle parsellenmesi MSD radix sort algoritması çalışır:
- Her tuşun en önemli basamağını atın.
- Biri içine aynı rakam ile elemanları gruplama, bu rakam dayalı öğelerin listesini sıralamak kova .
- Yinelemeli sonraki sağ haneye başlayarak, her kova sıralayın.
- concatenate için birlikte kova.
Recursive ileri radix sort örneği
Sıralama listesi:
170, 045, 075, 090, 002, 024, 802, 066
- En önemli basamağın (100s yeri) göre sıralama verir:
Sıfır yüzlerce kepçe: 0 45, 0 75, 0 90, 0 02, 0 24, 0 66
Bir yüzlerce kepçe: 1 70
Sekiz yüz kova: 8 02
- Bir sonraki haneye (10s yeri) tarafından sıralama sadece sıfır yüzlerce kova bu numaraları (başka kovalar birden fazla öğe içerir) için gerekli olan:
Sıfır onlarca kepçe: 0 0 2
Yirmili kova: 0 2 4
Kırklar kova: 0 4 5
Sixties kova: 0 6 6
Seventies kova: 0 7 5
Nineties kova: 0 9 0
Birden fazla numara ile herhangi bir on kova olarak orada tarafından en az önemli basamak (1s yeri) Sıralama, gerekli değildir. Bu nedenle, şimdi, kova birleştirilmiş sıfır yüzlerce sıralanmış vermek için tek yüz kova ve sekiz yüz kova ile, sırayla katıldı:
002, 024, 045, 066, 075, 090, 170, 802
Bu örnek kullanılan üssü okunabilirlik uğruna on basamak, ama tabii ki ikili basamak veya belki bayt ikili bilgisayar işlemek için daha mantıklı olabilir.
Yerinde MSD radix sort uygulamaları
0s bin ve 1'ler bin - de ikili quicksort denilen İkili MSD radix sort, iki bidonları içine girdi dizisini bölerek yerinde uygulanabilir.1s bin dizinin sonuna büyüdü oysa 0s bin, dizinin başlangıcından itibaren yetiştirilir. 0s bin sınır ilk dizi öğesinin önüne yerleştirilir. 1s bin sınır son dizi öğesinin sonra yerleştirilir. İlk dizi öğesinin en önemli biti incelenmiştir. Bu bit 1 ise, ilk unsur 1s bin sınırının önündeki elemanın (dizinin son elemanı) ile takas edilir ve 1s bin 1'ler sınır dizi indeksi azaltılmasıyla tek eleman tarafından yetiştirilir. Bu bit 0 ise, ilk öğe geçerli konumda kalır ve 0'lar bin bir eleman tarafından yetiştirilir.incelenen sonraki dizi öğesi 0'lar bin sınırının önünde bir (0'lar kutusu veya 1s bin değil yani ilk eleman) 'dir. 0s bin ve bin 1s birbirlerini ulaşana kadar bu işlem devam eder. 0s bin ve bin 1s sonra yinelemeli her dizi öğesinin sonraki bit dayalı sıralı almaktadır. En anlamlı bit sıralamak için kullanılana kadar Yinelemeli işleme devam eder. taşınması bit kalan işaretsiz işlenerek, ardından zıt olan en önemli bit tedavi gerektiren tamsayılar imza.
Yerinde MSD ikili sayı tabanı sıralama büyük radix uzatılabilir ve yerinde yeteneği. Muhafaza eden sayım sıralama her bin büyüklüğü ve başlangıç indekslerini tespit etmek için kullanılır. Swapping bin sınırını genişleterek ardından kendi kutusu içine geçerli elemanı, yerleştirmek için kullanılır. Dizi elemanları taranır gibi kutuları üzerinde atlanır ve tüm dizi işlendikten kadar bidonları arasındaki tek unsurlar işlenir ve tüm unsurları kendi kutularına sonuna kadar. bidonları sayısı kullanılan radix aynıdır - 16 Radix 16 bidonları örneğin. Her geçişte başlayarak tek haneli (örneğin, 16-Sayı tabanı olması durumunda her basamak için 4-bit) dayanır en önemli rakam . Tüm rakam sıralamak için kullanılmıştır kadar her bin, daha sonra ardışık bir sonraki basamağı kullanılarak işlenir.
Kararlı MSD radix sort uygulamaları
MSD Sayı tabanı Sıralama stabil algoritması olarak uygulanan, ancak girdi dizisi ile aynı boyutta olan bir bellek tampon kullanımını gerektirir. Bu ekstra bellek giriş tampon son ve aynı sırayla hedef kutularına dizi öğelerini taşımak için ilk dizi elemanı taranan sağlar. Böylece, eşit elemanlar giriş dizide olan aynı sırayla bellek tampon yerleştirilir. MSD-tabanlı algoritma geri girdi tampon çıktı sonucunu kopyalama yükü önlemek için, özyineleme ilk düzeyde çıkış olarak ekstra bellek tampon kullanır, ancak özyineleme sonraki seviyeye üzerinde giriş ve çıkış swapları. Yerinde MSD Radix sırala yapıldığı gibi bidonları her biri ardışık, işlenir. Son rakamı göre sırala tamamlandıktan sonra, çıktı tamponu orijinal giriş dizisi olup olmadığını görmek için kontrol edilir ve bu değilse, o zaman tek bir kopyası yapılır. Basamaklı boyutuna bölünmesiyle anahtar boyutu bir çift sayı olduğu basamaklı boyutu, seçilirse, son kopyalama önlenir.
Hibrid yaklaşımlar
Radix sıralama gibi iki geçişli yöntemi çeşit sayım özyineleme her düzeyde ilk geçiş sırasında kullanılan büyük bir sabite sahiptir. Kutuları küçük olsun Dolayısıyla, diğer sıralama algoritmaları gibi, kullanılması gereken sokma tür. Iyi bir uygulama yerleştirme tür küçük diziler, istikrarlı, yerinde hızlı ve önemli ölçüde Radix Sıralama hızlandırabilir.
Uygulama bilgisayar paralel
Bu özyinelemeli sıralama algoritması için özel bir uygulama olduğunu unutmayın parelel hesaplama kovaları her biri bağımsız olarak sıralanabilir olarak. Bu durumda, her bin bir sonraki işlemciye iletilir. Tek bir işlemci başlangıcı (en önemli basamak) olarak kullanılacaktır. Ikinci veya üçüncü rakam ile, mevcut tüm işlemciler büyük olasılıkla meşgul olacaktır. Her alt bölümü tamamen sıralanır İdeal olarak, daha az ve daha az işlemci kullanılabilir olacaktır. En kötü durumda, tüm tuşları anahtarları sıralamak için paralel işlem kullanılarak herhangi bir avantaj az olacaktır ve sonuç olarak, aynı ya da birbirine hemen hemen aynı olacaktır.
Özyineleme üst düzeyde, paralellik fırsatı olduğunu sayım sıralama algoritmasının kısmı. Sayma parallel_reduce desenine mükellef, son derece paralel ve bellek bant genişliği sınırına ulaşana kadar çoklu çekirdek arasında iyi işi böler.Algoritmanın bu bölümü veri bağımsız paralellik vardır. Daha sonra yineleme seviyeleri, her bin işlenmesi ancak veri bağlıdır. Tüm tuşlar aynı değerde olsaydı Örneğin, o zaman orada o herhangi elemanları ile tek bir kutu olurdu ve hiçbir paralellik kullanılabilir olacaktır. Rastgele girişler için tüm kutuları yakın eşit nüfuslu olacak ve paralellik fırsat büyük miktarda kullanılabilir olacaktır.
Hızlı sıralama algoritmaları kullanılabilir olduğunu unutmayın
Incremental tray tabanlı radix sort
Bir MSD radix sıralama ile devam etmek için başka bir yolu oluşturmak için daha fazla bellek kullanmak için tray anahtarlarını temsil ve ardından sırayla her tuşa ziyaret tray çapraz. Bir derinlik birinci geçişi başlayarak trayın kök düğüm sırayla her tuşa ziyaret edecek. Bir tray bir derinlik ilk geçişi, ya da başka türlü asitlik ağaç yapısı aracılığıyla bir labirent geçme eşdeğerdir
Bir tray aslında bir temsil kümesi dizeleri veya sayı ve tray yapısını kullanan bir radix sort bir dizi yinelenen öğeleri içermediği için yinelenen tuşları orijinal düzeni mutlaka korunmaz anlamına gelir mutlaka istikrarlı değildir. Ek bilgiler bu bilgilerin kaydını tutmak belirli bir uygulama için önemli ise bir tray tabanlı radix tür nüfus sayımı ya da herhangi bir yinelenen tuşları orijinal düzenini belirtmek için her tuş ile ilişkili gerekecektir. Gol sıralı sırayla yalnızca benzersiz dizeleri bulmak için ise bile tray oluşturma ilerledikçe herhangi bir yinelenen dizeleri atmak istenebilir. Bazı insanlar ilk dizeleri listesini sıralamak ve daha sonra aynı anda sıralamak ve tek geçişte çift dizeleri atmak için bir tray kullanmaktan daha yavaş olabilir yinelenen dizeleri, atmak sıralanmış liste içinde ayrı bir geçiş yapmak.
Tray yapısını koruyarak avantajlarından biri tray belirli bir anahtar, anahtar, uzunluğuna orantılı olan bir süre içinde şifreler grubu üyesi ise, hızlı bir şekilde tespit edilmesini mümkün kılar ki , k (Ç, k olduğu) zaman, bağımsız olarak şifreler toplam sayısı. Bir tray set üyeliği belirleyen aksine, düz bir liste set üyeliği belirlenmesi gerektiren ikili arama , O ( k log (n) ) zaman,doğrusal arama , O ( kn ) zaman; ya da kimin yürütme zamanı bir şekilde diğer bazı yöntem bağımlı toplam sayısına, n , anahtarların en kötüsü durumunda. Bu O (bir düz bir liste set üyeliğini belirlemek için bazen mümkün olabilir k gibi liste, bir de olduğu bilinmektedir olduğu gibi tuşların toplam sayısı, bağımsız bir süre içinde) zaman aritmatik dizisini veya başka hesaplanabilir dizisi .
Tray yapısını koruyarak da mümkün aşamalı dizi içine yeni anahtarlar eklemek veya O (içinde sıralanmış düzeni koruyarak adım adım ise kümesinden anahtarları silmek için yapar k tuşlarının toplam sayısının bağımsız bir süre içinde) zaman.Buna karşılık, diğer radix sıralama algoritmaları gerekir, anahtarları yeni bir anahtar O (gerektiren eklenen veya varolan listeden silinir her zaman en kötü durumda, yeniden sıralama Tüm listeyi kn ) zaman.
Snow White benzetme
Düğümler koridorları ile bağlantılı oda olsaydı, o zaman burada Snow White yeri her zaman duvara sağ elini tutarak, karanlık olsaydı cüceler tüm ziyaret devam olabileceğini nasıl:
- O Bashful bulmak için salon B aşağı hareket eder.
- O odanın etrafında onu alır duvarda, onu sağ eli ile ilerliyor ve salon B. yedeklemek devam
- O Doc bulmak için salonlar D, O ve C aşağı doğru hareket eder.
- Sağ eliyle duvarı takip sürdüren o geri salon C, sonra o Dopey bulur salon P, aşağı yukarı gider.
- O geri salonları P, O, D yukarı devam ediyor ve sonra Grumpy bulmak için salon G iner.
- O duvarda hala sağ eliyle geri salon G kadar gider ve mutlu bir odaya salon H iner.
- O salon H geri hareket eder ve o Sleepy bulduğu yerde, doğru salonları S ve L aşağı döner.
- O nihayet Sneezy bulur salon N, aşağı, geri salon L kadar gider.
- O başlangıç noktasına geri salonları, N ve S yedekleme seyahatleri ve o yapılır biliyor.
Adımlar bu serisi aracılığıyla Snow White tarafından traya alınan yolu göstermek için hizmet deinliği ilk geçişi isimlerini, Utangaç, Doc, unutkan, Grumpy, Mutlu, Sleepy ve Sneezy yükselen emriyle cüceler ziyaret etmek. Bu tür veri yazdırma ve ardından denir ağaca derinlerine doğru ilerleyerek ilk olarak bir ağacın her düğüm ile ilişkili veriler, bazı işlem gerçekleştirmek için algoritma ön şipariş geçişi bir tür, derinlik ilk geçişi . Ön sipariş geçişi düzeni artan bir tray içeriğini işlemek için kullanılır. Snow White isimleri azalan emriyle cüceler ziyaret etmek isteseydim onu sağ eli ile duvarı takip ederken, sonra o geriye yürüyebiliyordu veya sol eliyle duvarı takip ederken alternatif ileri yürüyün. edilmemiş düğümlere daha fazla iniş mümkün olana kadar ilk bir ağacın derinlerine doğru ilerleyerek ve daha sonra her bir düğüm ile ilişkili veriler üzerinde bazı işlem gerçekleştirmek için algoritma denir post-order geçişi derinliği ilk geçişi bir başka türüdür. Bir post-sırası geçişi azalan bir tray içeriğini işlemek için kullanılır.
kök düğüm arasında traya diyagramı esasen boş bir dize, bir kelime listesinde boş satır sayısı izleyebilmek için yararlı olabilir boş bir dize, temsil eder. Boş dize dairesel ile ilişkili olabilir bağlantılı listede hem başlangıçta boş bir dize işaret ileri ve geri işaretçileri ile başlangıçta tek üyesi olarak boş bir dize ile. Her yeni bir anahtar yerleştirildiğinde, dairesel bağlantılı liste daha sonra genişletilebilir tray . dairesel bağlantılı liste aşağıdaki diyagram olarak kalın, gri, yatay bağlantılı hatlar temsil edilmektedir:
Boş bir dize dışında yeni bir anahtar, bir takılıysa yaprak düğümün bir tray , ardından bilgisayar gerçekleştirmek için bir anahtar veya çatallanma orada son önceki düğüme gidebilirsiniz derinliği ilk arama lexicographic bulmak için halef veya dairesel yeni anahtar eklenerek birleştirilmesi amacıyla eklenen anahtar selefi bağlantılı liste . Bir anahtar ya da bir çatallanma, yolda bir çatal vardı son önceki düğüm, bir olan üst düğüm yalnızca benzersiz dize önek tray de yolları olarak temsil edilir Burada gösterilen tray türüne de. Zaten bir hareket sırasında ziyaret olurdu ana düğüm ile ilişkili anahtar varsauzak bir sağ el, ileri hareketli, derinlik ilk geçişi sırasında kök, o hemen bu kadar, derinlik ilk arama sona erer Anahtar takılı anahtar selefi olduğunu. Bashful tray içine sokulur Örneğin, ardından selefi olan ebeveyn düğümü null dize kök düğümübu durumda. Yerleştirilmiş olan kilit üst düğümün en soldaki dalında ise, başka bir deyişle, daha sonra, ana düğümünde yer alan herhangi bir dize takılı olan anahtarın lexicographic öncülü olan anahtarın başka lexicographic öncülüdür takılı olan yeni anahtar takılı olan şube hemen solunda olan ana düğümün şube aşağı var. Huysuz tray sokulan son tuşa olsaydı Örneğin, daha sonra bilgisayar ile selefi, Dopey veya halefi, Mutlu ya bulmaya çalışırken bir seçim, olurdu derinlik öncelikli arama Grumpy ana düğümün başlayarak . Yol uzun olduğu göstermek için hiçbir ek bilgiler sayesinde, bilgisayar uzun bir yol, D hareket olabilir, O, P unutkan Eğer tray sokulan son tuşa vardı derinlik öncelikli arama unutkan ana düğüm olur başlayan sadece seçim olurdu, çünkü yakında, selefi "Doc" bulmak.
Yeni bir anahtar, bir takılıysa iç düğümün , sonra bir derinlik öncelikli arama başlatılabilir iç düğümün lexicographic halef bulmak için. Değişmez dize "DO" Örneğin, bir amaç için, halefi, "DOC" bulmak için D, O, daha sonra bir derinlik öncelikli arama, iç düğümden başlamış olabilir yolun sonuna düğümünde yerleştirildi
Dairesel bağlantılı liste oluşturulması daha fazla bellek gerektirir ama tuşları doğrusal geçişi yoluyla artan veya azalan sırayla ya daha doğrudan ziyaret sağlar bağlantılı listeden ziyade bir derinliği ilk geçişi tüm tray. Bir dairesel bağlantılı tray yapısı bu kavram kavramı benzer dişli ikili ağacın . Bu yapı, bir dairesel dişli tray çağrılır.
Bir zaman tray numaralarını sıralamak için kullanılan bir gerçekleştirmek için istekli olmadıkça, sayı gösterimleri hepsi aynı uzunlukta olmalı genişlik-ilk geçişi . Sayı temsilleri aracılığıyla ziyaret edilecektir zaman derinliği ilk geçişi , yukarıdaki şekilde olduğu gibi, sayı temsiller her zaman olacaktır yaprak düğümlerin bir tray . Ne kadar bir tray bu özel örneği kavramı içindeki Not yinelemeli ileri radix sıralama örneğin yerine tray kova kullanımını içerir. Kova ile radix tür gerçekleştirme tray oluşturma ve daha sonra Yaprak olmayan düğümleri atarak gibidir.
