Sayarak Sıralama (Counting Sort)

,Yazan : Şadi Evren ŞEKER

Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Basitçe sıralanacak olan dizideki her sayının kaç tane olduğunu farklı bir dizide sayar. Daha sonra bu sayıların bulunduğu dizinin üzerinde bir işlemle sıralanmış olan diziyi elde eder.

Sıralanmak istenen verimiz:

5,7,2,9,6,1,3,7

olsun. Bu verilerin bir oluşumun(composition) belirleyici alanları olduğunu düşünebiliriz. Yani örneğin vatandaşlık numarası veya öğrenci numarası gibi. Dolayısıyla örneğin öğrencilerin numaralarına göre sıralanması durumunda kullanılabilir.

Bu dizi üzerinden bir kere geçilerek aşağıdaki sayma dizisi elde edilir:

Dizi indisi:	0	1	2	3	4	5	6	7	8	9
Değeri (sayma):	0	1	1	1	0	1	0	2	0	1

Yukarıdaki tabloda da gösterildiği üzere dizide bulunan en büyük eleman sayısı kadar eleman içeren bir sayma dizisi oluşturulmuş ve bu dizinin her elemanına, sıralanmak istenen dizideki her elemanın sayısı girilmiştir.

Bu sayma işleminden sonra sıralı dizinin üretilmesi yapılabilir. Bu işlem de dizinin üzerinden tek bir geçişle her eleman için kaç tekrar olduğu yazılarak yapılabilir. buna göre örneğin sıralanmış dizide 0 hiç olmayacak 1′den 1 tane, 2′den 2 tane olacak şeklinde devam eder ve sonuç:

1,2,3,5,7,7,9

şeklinde elde edilir.

Bu sıralama algoritmasının JAVA dilindeki kodu aşağıda verilmiştir:

public static void countingsort(int[]A, int[]B, int k)
{
int C[]=new int[k]; // sayma dizisi oluşturuluyor
int i;
int j;

for(i=0; i<k; i++)
{
C[i]=0;
}
for(j=0; j<A.length; j++)
{
C[A[j]]=C[A[j]]+1 ;
}
for(i=1; i<k; i++)
{
C[i]=C[i]+C[i-1];
}
for(j=0; j<A.length; j++)
{
B[C[A[j]]]=A[j];
C[A[j]]=C[A[j]]-1;
}
}

Yukarıdaki fonksiyon bir adet sıralanacak dizi, bir adet sıralanmış hali geri döndürecek atıf ile çağırma (call by reference ile) boş dizi ve dizideki en büyük sayının değerini alır. Sonuç ikinci parametre olan boş diziye döner.

Bu sıralama algoritmasının karmaşıklığı (complexity) hesaplarnısa. Dizideki her elemanın üzerinden bir kere geçilerek sayıları hesaplanır. Bu geçiş n elemanlı dizi için n zaman alır. Ayrıca dizideki en büyük elemanlı sayı kadar (bu örnekte k diyelim) büyük olan ikinci bir sayma dizisinin üzerinden de bir kere geçilir bu işlem de k zaman alır. Dolayısıyla toplam zaman n+k kadardır. Bu durumda zaman karmaşıklığı O(n) olur.

Hafıza karmaşıklığına baklırsa (memory complexity) hafızada mevcut verilerin saklandığı bir dizi (yukarıdaki örnek kodda A dizisi). Sonuçların saklandığı ikinci bir dizi (yukarıdaki örnekte B dizisi) ve her elemanın kaçar tane olduğunun durduğu bir dizi (yukarıdaki örnekte C dizisi) tutulmaktadır. Bu durumda A ve B dizileri n, C dizisi ise k boyutundadır ve toplam hafıza ihtiyacı 2n+k kadardır.

« Kabarcık Sıralaması (Baloncuk sıralaması, Bubble Sort) | Nöbetçi (Sentinel) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Sayarak Sıralama (Counting Sort)' isimli yazı 09 Aug 2008 tarihinde, saat: 20:17 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 1765 defa okunmuştur.

Benzer yazıları C/C++, JAVA, algoritma analizi (teory of algorithms), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar