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.
