COUNTİNG SORT ALGORİTMASI

COUNTİNG SORT ALGORİTMASI

Counting sort Algoritması Türkce olarak sayarak sıralama olarak söylebiliriz

Sıralanmak istenen verimiz:

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

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.

JAVA KODUNU VERELİM

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  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ığı hesaplarnırsa. 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 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.