مرتب‌سازی شمارشی

مرتب‌ساز شمارشی، یک مرتب‌ساز پایدار است و دارای زمان اجرای (Θ(n+k است که n و k به ترتیب، طول‌های آرایه‌های A (آرایه ورودی) و C (آرایه شمارشی) هستند. برای این که الگوریتم، کارآمد باشد، k نباید خیلی بیشتر از n باشد.

اندیس‌های C، باید از کوچکترین تا بزرگترین عناصر A باشند تا بتوان C را به صورت مستقیم با مقادیر A، اندیس‌گذاری کرد. در غیر این صورت، مقادیر A باید انتقال (شیفت) داده شوند تا کمترین مقدار A، معادل کوچکترین اندیس C شود. اگر بیشتری و کمترین مقادیر A معلوم نباشند، باید توسط یک الگوریتم انتخاب، که زمان (Θ(n می‌گیرد، آنها را پیدار کرد. طول آرایه شمارشی C، حداقل باید برابر بازه اعداد ورودی باشد. (کمترین منهای بیشتری و به‌اضافه ۱). این ویژگی باعث می‌شود که استفاده از مرتب‌ساز شمارشی برای بازه‌های بزرگ اعداد، غیرعملی شود. مرتب‌ساز شمارشی، برای مثال، می‌تواند بهترین الگوریتم برای اعدادی باشد که بین ۰ و ۱۰۰ قرار دارند. این الگوریتم برای مرتب کردن اسامی بر اساس حروف الفبا، نامناسب است (مراجعه شود به مرتب‌ساز سطلی و مرتب‌ساز لانه‌کبوتری).

به علت اینکه مرتب‌ساز شمارشی، از مقادیر به عنوان اندیس آرایه استفاده می‌کند، یک الگوریتم مرتب‌ساز مقایسه‌ای، نیست و بنابراین کران پایین (Ω(n log n برای این الگوریتم قابل تطبیق نیست.

1. کوچکترین و بزرگترین عناصر مجموعه را پیدا کن.
2. مقادیر مختلف موجود در آرایه را بشمار. (برای مثال، مجموعه [۴،۴،۴،۱،۱] دارای سه تا ۴ و دو تا ۱ است)
3. شمارش‌ها را جمع کن.
4. آرایه مقصد را از انتها پر کن: هر عنصر را در موقعیت countام قرار بده.
   هر موقع که عنصری را درج می‌کنی، شمارشش را یکی کم کن.

پیاده‌سازی با سی++

/// countingSort - sort an array of values.
///
/// For best results the range of values to be sorted
/// should not be significantly larger than the number of
/// elements in the array.
///
/// param nums - input - array of values to be sorted
/// param size - input - number of elements in the array
///
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;
}

....

Wikipedia contributors, "Counting sort," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Counting_sort&oldid=209333915