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

مرتب‌ساز شمارشی یکی از الگوریتم‌های مرتب‌سازی است که (مثل مرتب‌ساز سطلی) با فرض دانستن بازه اعداد داخل آرایه (A)، عمل مرتب‌سازی را انجام می‌دهد. این الگوریتم از این بازه برای ساختن یک آرایه (C) با این طول استفاده می‌کند. هر اندیس i در آرایه C برای شمارش تعداد عناصر A که دارای مقدار i هستند، به کار می‌رود. این اعداد در C برای قرار دادن عناصر A در جای درستشان در آرایه خروجی، به کار می‌روند. مرتب‌ساز لانه‌کبوتری از این الگوریتم، کارآمدتر است.

ویژگی‌های مرتب‌ساز شمارشی

مرتب‌ساز شمارشی، یک مرتب‌ساز پایدار است و دارای زمان اجرای (Θ(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