Sıralama Algoritmaları - 4. Basamağa Göre Sıralama (Radix Sort)

Basamağa göre sıralama (İngilizcesi: Radix sort) bilgisayar bilimlerinde sayıları basamaklarının üzerinde işlem yaparak sıralayan bir sıralama algoritmasıdır.

İngilizce Adı Radix Sort
Ortalama O(n x k/s)
En kötü O(n x k/s)
Bellek O(n)
Kararlı mı? Evet / Hayır *
Yöntem Karşılaştırmadan Sıralayan

Basamağa göre sıralama (İngilizcesi: Radix sort) bilgisayar bilimlerinde sayıları basamaklarının üzerinde işlem yaparak sıralayan bir sıralama algoritmasıdır. Sayma sayıları adlar ya da tarihler gibi karakter dizilerini göstermek için kullanılabildiği için basamağa göre sıralama algoritması yalnızca sayma sayılarını sıralamak için kullanılan bir algoritma değildir.

Çoğu bilgisayar veri saklamak için ikilik tabandaki sayıların elektronikteki gösterim biçimlerini kullandığı için 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 anlamlı basamağa göre sıralama ve en anlamsız 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 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 "anahtar" denir. En anlamsız basamağa göre sıralamada kısa anahtarlardan 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 dizgileri 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.

Kod örneği

public class BasamagaGoreSiralama
{
int[] dizi;
public int[] Dizi
{
	get { return dizi; }
	set { dizi = (int[])value.Clone(); }
}
public BasamagaGoreSiralama()
{
	//
	// TODO: Add constructor logic here
	//
}

public void Sirala()
{
	RadixSort();
}

public override string ToString()
{
	return "Basamağa Göre Sıralama";
}

public void RadixSort()
{
	// our helper array 
	int[] t = new int[Dizi.Length];

	// number of bits our group will be long 
	int r = 4; // try to set this also to 2, 8 or 16 to see if it is quicker or not 

	// number of bits of a C# int 
	int b = 32;

	// counting and prefix arrays
	// (note dimensions 2^r which is the number of all possible values of a r-bit number) 
	int[] count = new int[1 << r];
	int[] pref = new int[1 << r];

	// number of groups 
	int groups = (int)Math.Ceiling((double)b / (double)r);

	// the mask to identify groups 
	int mask = (1 << r) - 1;

	// the algorithm: 
	for (int c = 0, shift = 0; c < groups; c++, shift += r)
	{
		// reset count array 
		for (int j = 0; j < count.Length; j++)
			count[j] = 0;

		// counting elements of the c-th group 
		for (int i = 0; i < Dizi.Length; i++)
			count[(Dizi[i] >> shift) & mask]++;

		// calculating prefixes 
		pref[0] = 0;
		for (int i = 1; i < count.Length; i++)
			pref[i] = pref[i - 1] + count[i - 1];

		// from Dizi[] to t[] elements ordered by c-th group 
		for (int i = 0; i < Dizi.Length; i++)
			t[pref[(Dizi[i] >> shift) & mask]++] = Dizi[i];

		// Dizi[]=t[] and start again until the last group 
		t.CopyTo(Dizi, 0);
	}
	// a is sorted 
}
}