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 | 1 | 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 1 tane olacak şeklinde devam eder ve sonuç:
1,2,3,5,6,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.
Merhaba ,
5,7,2,9,6,1,3,7 bu sayılarla işlem yaparken
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
yazılmış.Fakat 6 dan da 1 tane olması gerekmiyor mu ?
Bir de
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ç:
kısmında 2’den 1 tane olucak şeklinde devam eder olmayacak mı ?
Kolay gelsin
İyi çalışmalar
Haklısınız yazıda ilgili düzeltmeleri yaptım.
ilginiz için teşekkürler
Hocam Merhabalar
Kodun,
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; } }kısmının nasıl çalıştığını anlatabilir misiniz acaba ? özellikle
for(i=1; i<k; i++) { C[i]=C[i]+C[i-1]; }burası
en baştan başlayarak her sayıya kendinden önce gelen sayı ekleniyor farkındayım fakat neden ?
Elbette. Durum kısaca şu şekilde, her sayı için kaçar tane olduğunu saydığımız dizi C dizisi. Bunları sıralı bir şekilde döndüreceğiz ancak eleman sayılarının yanında eleman değerleri de önemli.
Örneğin dizimiz sadece 2 ve 3 sayılarından oluşsun. 3, 2’den büyük olduğu için dizideki konumu önemli olmaksızın sıralanmış halde 2’nin sağında olmalı. Dolayısıyla C dizi öncelikle her elemandan kaçar tane olduğunu sayıyor sonra her elemana, elemandan daha küçük olanların sağında olacak şekilde değer atıyor. Bahsettiğiniz kısım çalıştıktan sonra aslında her sayının sonuç dizisindeki adresi belirlenmiş oluyor. Yani 2 ve 3’ten oluşan dizimiz için 2 birinci sırada 3 ise ikinci sırada şeklinde. Şayet bir sayıdan elimizde hiç yoksa diğer sayı bunu eziyor (çünkü aynı adrese sahip oluyorlar).
Bu Java kod parçasındaki fonksiyonun main içerisinde çağırılmasından sonra ArrayIndexOutOfBoundException hata mesajı vereceğini düşünüyorum. Yalnız, bu kod parçasını sadece konu anlatımı amaçlı koyduysanız sıkıntı yoktur. Saygılar.
yarım saattir anlamadığım algoritmayı 3 dakikalık videonuzda anlayıp aklıma takılan yeri ve cevabını da yorumda gördüm ya ne deyim.Sağolun varolun hocam emeğiniz için minnettarız.
merhaba bir sorum olacaktı peki aynı elemanları hangi sıralama algoritması ile sıralarız mesela 5,5,5,5,5,5,5 dizisinin elemanlarını ve buna ek olarak sıfırları hangi algoritma ile sıralarız 0,0,0,0,0 gibi bir diziyi yardımcı olur musunuz?