Sayarak sıralama

Sayarak sıralama bilgisayar bilimlerinde kullanılan ve kova sıralaması gibi sıralanacak dizinin içindeki değerlerin aralığının bilinmesi durumunda kullanılabilen bir sıralama algoritmasıdır. Sayarak sıralama algoritması dizideki değerlerin aralık bilgilerini yeni bir dizi oluşturmak için kullanır. Oluşturulan yeni dizinin her bir satırı ana dizide o satır numarasının değerine sahip ögelerin sayısını gösterir. Yeni dizideki öge değeri sayıları daha sonra ana dizideki tüm değerlerin doğru konuma konulması için kullanılır. Sayarak sıralama algoritması güvercin yuvası sıralamasından daha verimsiz bir algoritmadır.

C++ ile uygulaması

Aşağıdaki program sayarak sıralama algoritmasının C++ dilinde yazılmış bir uygulamasını göstermektedir.

/// countingSort - değerleri tutan bir diziyi sıralamak için.
///
/// Algoritmanın verimli çalışması için sıralacak 
/// değerlerin aralığı sıralanacak ögelerin sayısından
/// çok daha büyük olmamalıdır.
/// 
/// param nums - girdi - sıralanacak değerler dizisiǖ
/// param size - girdi - dizideki ögelerin sayısı
///
void counting_sort(int *nums, int size)
{
	// search for the minimum and maximum values in the input
	int i, min = nums[0], max = min;
	for(i = 1; i < size; ++i)
	{
		if (nums[i] < min)
			min = nums[i];
		else if (nums[i] > max)
			max = nums[i];
	}
	
	// create a counting array, counts, with a member for 
	// each possible discrete value in the input. 
	// initialize all counts to 0.
	int distinct_element_count = max - min + 1;
	int*counts = new int[distinct_element_count];
	for(i=0; i<distinct_element_count; ++i)
		counts[i] = 0;
	
	// accumulate the counts - the result is that counts will hold
	// the offset into the sorted array for the value associated with that index
	for(i=0; i<size; ++i)
		++counts[ nums[i] - min ];
	
	// store the elements in the array
	int j=0;
	for(i=min; i<=max; i++)
		for(int z=0; z<counts[i-min]; z++)
			nums[j++] = i;

        delete[] counts;
}