اول از همه عید تون شاد باد این پست هم به مناسبت عید ایجاد کردم تا شب عید بدون پست نباشیم . در این پست یکی دیگه از روش های مرتب سازی بررسی می کنیم که با روش های قبلی فرق دارد. روش های قبلی بر اساس مقایسه بود و المنت های توی تابع با هم مقایسه می شدند و  بعد از مقایسه عنصر ها جایشان عوض می شد . در الگوریتم  های مرتب  سازی بر اساس مقایسه هزینه الگوریتم بین n^2 , n Lg n بود ولی الگوریتم مرتب سازی شمارشی (Counting Sort) از درجه n است و به آن مرتب سازی خطی (Linear Sort) می گویند چون براساس مقایسه نیست! البته با اینکه سرعت خوبی داره ولی حافظه زیادی می گیرد.

قبل از شرح الگوریتم مروری کنیم بر مباحثی که بررسی کردیم و می خواهیم بررسی کنیم :

– مفهوم مرتب سازی

–bubble sort

-insertion sort

-merge sort

–quick sort

-Distribution sorts

– Concurrent sorts

– Heap sort

-Radix sort

– Counting sort

فرض کنید آرایه پنج عضوی  A

4,1,3,4,3

را داریم و می خواهیم  آن را با مرتب سازی شمارشی مرتب کنیم ، ابتدا در آرایه  جست و جو می کنیم و بزرگ ترین عضو آرایه را پیدا می کنیم و یک آرایه با طول بزرگترین عضو آرایه به علاوه یک می سازیم.اگر بزرگ ترین عضو A را در متغییر Max برزیم ما آرایه ای به طول Max+1  می سازیم و اسم آن را B می گذاریم و همه ی خانه های آن را صفر می کنیم.

آرایه B به طول پنج:

0,0,0,0,0

مرحله  بعد  مرحله شمارش یا همون counting است که از اول آرایه A شروع به حرکت می کنیم  .اولین خانه آرایه  A  مقدار چهار است بعد از خواندن ۴ از آرایه A

به خانه ی چهارم به علاوه یک آرایه  B  می رویم و مقدار آن را یکی افزایش می دهیم
آرایه جدید B :

0,0,0,0,1

بعد به خانه ی بعدی در آرایه A می رویم که مقدار آن یک است و ما بعد از خواندن یک به خانه ی اول  به علاوه یک آرایه B  می رویم و مقدار آن را به علاوه ی یک می کنیم:

آرایه B :

0,1,0,1,0

و همین طوری در آرایه A پیش می رویم و تعداد هر کدام از عناصر را می شماریم و در آرایه B می ریزیم.

آرایه B بعد از شمارش همه ی اعضای درون A:

0,1,0,2,2

بعد از پر کردن آرایه B و پر کردن آن با تعداد اعضای A ، فراوانی اعضای A را در B بدست می آوریم  برای این کار اعضای آرایه B را با عضو های قبلی جمع می کنیم
آرایه  B بعد از جمع عضوهایش:

0,1,1,3,5

در مرحله ی بعد که مرحله آخر است یک آرایه دیگر هم اندازه A به اسم C می سازیم و از آخرین خونه A شروع می کنیم و به اول آرایه می آییم .خانه ی آخر آرایه A عدد ۳ است و به خانه ی سه به علاوه  یک درون آرایه B می رویم که  مقدار سه درون آن است یکی از آن کم می کنیم و بعد به خانه سه منهای یک درون آرایه C می رویم و مقدار ۳ را درون آن می گذاریم:

آرایه C:

0,0,3,0,0

و این  کار را ادامه می دهیم.

آرایه نهایی C :

1,3,3,4,4

این هم کد برنامه مرتب سازی شمارشی – counting sort

// Counting Sort (for int number).cpp 
//

#include "stdafx.h"
#include <iostream>
using namespace std;

void counting_sort( int A[], int n)
{
	int i;
	int Max = A[0];
	int *B;
	int *C;
	//found Max number in array
	for ( i = 1; i < n; i++)
	{
		if(Max < A[i])
		{
			Max = A[i];
		}
	}
	//Define array that lenght is Max
	B = new int [Max+1];
	//set 0 all array
	for ( i = 0; i <= Max; i++)
	{
		B[i] = 0;
	}
	//
	for ( i = 0; i < n; i++)
	{
		B[ A[i]] ++;
	}
	//
	for ( i = 1; i <= Max; i++)
	{
		B[i] = B[i] + B[i-1];
	}
	//make new array for insert sorted number in it
	//open-mind.ir
	C = new int [n];
	//
	for ( i = n-1; i >= 0; i--)
	{
		C[ B[ A[i]]-1] = A[i];
		B[ A[i]]--;
	}
	//put C in A and delet C from memory
	for ( i = 0; i < n; i++)
	{
		A[ i] = C[ i];
	}
}

int main()
{
	int i;
	int A[10] = {9,5,6,8,9,0,3,2,3,0};
	counting_sort(A,10);

	//Print A after sort
	for ( i = 0; i < 10; i++)
	{
		cout<<A[i]<<" ";
	}
	cout<<endl;
	//
	return 0;
}