Sayarak Sıralama

     Sayarak Sıralama

Adını sıkça duyduğum , ama ancak geçen hafta tanıştığım Sayarak(Counting) Sıralama algoritmasını size tanıtmak istiyorum.En iyi ihtimalle worst case O(n logn) çalışan heap sort merge sort gibi algoritmaların aksine counting sort linear time da yani O (n) de çalışır.Ancak counting sort'u kullanabilmemiz için bazı şartlar vardır.Bunlara gelirsek sıralanan elemanların hepsinin integer veri tipinde olması gerekir , ayrıca dizideki en büyük elemanıda bilmemiz gerekiyor ve en son olarak da eşitlik durumlarını umursamamız gerekir.Yani normalde x<=y veya x>=y gibi sınamalar yaparken burada sadece x<y veya x>y durumlarını umursayacağız.

Algoritmanın işleyiş biçimine gelirsek de ; iki tane extra dizi ye ihtiyacımız olacak bu algoritmayı kullanırken bunlardan output için kulllanılanına B geçici işler için kullanacağımıza C dizisi ,standart sıralanmak istenen diziye de A dizisi diyelim.B dizisi sıralamak istediğimiz dizinin boyutunda boş bir dizi olarak tanımlı olmalıdır C dizisi ise k = en büyük sayı boyutunda olan bir dizi olacakdır.Burdaki k ya sayma numarası (counting number)da denilir.C nin bütün elemanlarına varsayılan olarak 0 elemanı atanır ardından dizinin tüm indexleri sırayla gezilerek o index numarasından A dizisinde kaç kere bulunduğu sayılarak her elemana işlenir.

Ardından zurnanın zırt dediği yere geliyoruz.Burada ise C dizisinde bir değişiklik daha yapacağız.İndex numarasının kaçıncı indexe kadar B dizisine yazılacağanı temsil eden bir C dizisi oluşturuyoruz.

for i=0 to k

int C[i] = 0

for j = 1 to A.lenght

C[A[j]]=C[A[j]] + 1

//üstteki resimdeki işlemler yapıldı

for i=1 to k

C[i] = C[i]+C[i-1]

//bu adımda da o index numarasındaki sayıdan küçük o dizide kaç kere başka sayının olduğunun hesabını yapıp bu verileri C dizisine işliyoruz

En son ve basit olarak da tek tek sayıları bulundukları sayılar gereğince B dizisine yerleştirerek sıralamayı sonlandırmış oluyoruz.