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.

Yorumlar

  1. Barış

    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

  2. Faruk Yılmaz

    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ı

  3. Faruk Yılmaz

    en baştan başlayarak her sayıya kendinden önce gelen sayı ekleniyor farkındayım fakat neden ?

  4. Şadi Evren ŞEKER

    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).

  5. Gürbüz Aylin

    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.

  6. Yarın Vizesi Olan Şahıs

    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.

  7. baran

    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?

Faruk Yılmaz için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir