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

**مرتب‌ساز شمارشی** یکی از الگوریتم‌های مرتب‌سازی است که (مثل مرتب‌ساز سطلی) با فرض دانستن بازه اعداد داخل آرایه (*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* برای این الگوریتم قابل تطبیق نیست.

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

### پیاده‌سازی با [[سی++]]

```cpp
/// 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

رده:الگوریتم‌های مرتب‌سازی
رده:مرتب‌سازی‌های پایدار