counting sort یکی از الگوریتم های مرتب سازی هستش که بر خلاف مرتب سازی هایی مثل quick sort که با مقایسه عناصر انجام میشن از شمارش عناصر استفاده میکنه .
یکی از قضیه های اثبات شده این هستش که با الگوریتم هایی که از مقایسه استفاده می کنن نمیشه به مرتبه ای کمتر از nlogn رسید
مرتبه اجرا counting sort خطی و O(n هستش ولی 2 تا مشکل هم داره :
counting sort فقط برای مرتب سازی اعداد صحیح و غیر منفی کاربرد داره (میشه بعضی وقت ها چیزای دیگه رو هم map کرد به اعداد صحیح مثلا فرض کنید بیت های یک عدد که به شکل 01101 و ... هستن رو میشه هر حالت بیت رو به یک عدد صحیح نسبت داد و از این الگوریتم استفاده کرد)
در counting sort باید سعی بشه فاصله بین کوچیک ترین و بزرگنرین عنصر خیلی بزرگ نباشه .(در غیر این صورت هم حافظه زیادی مصرف میشه هم سرعت کمتر میشه )
نحوه عملکرد این الگوریتم :
فرض کنید یک آرایه داریم به این شکل :
3,3,2,7,4,1
یک آرایه دیگه به اندازه بزرگترین عنصر آرایه بالا میسازیم
_ _ _ _ _ _ _ _
تعداد دفعات تکرار هر کدوم از عناصر آرایه اول رو میزاریم داخل اندیس معادل آرایه ای که ساختیم
1,0,0,0,1,2,1,1
حالا یک آرایه برای ذخیره خروجی میسازیم
آرایه ای که تعداد داخلش هست رو پیمایش می کنیم هر جا که عدد بیشتر از 0 بود به آرایه خروجی به همون تعداد عدد رو اضافه می کنیم و آرایه مرتب شده بدست میاد
1و2و3و3و4و7
کد الگوریتم بالا به این شکله:
#include <iostream>
#include <cstring>
#include <algorithm>
void countingSort(int *arr,const int n)
{
int max=*(std::max(arr,arr+n));
int* counts=new int[max+1];
memset(counts,0,(max+1)* sizeof(counts[0]));
for(int i=0;i<n;i++)
counts[arr[i]]++;
int loc=0;
for(int i=0;i<max+1;i++)
{
while(counts[i]!=0)
{
counts[i]--;
arr[loc++]=i;
}
}
delete[] counts;
}
int main()
{
int arr[]={3,3,2,7,4,1};
countingSort(arr,sizeof(arr)/sizeof(arr[0]));
for(auto i:arr)
std::cout<<i<<"\n";
}
دقت کنید که الگوریتم و کد بالا ورژن unstable این الگوریتمه ( unstable یعنی در صورت برابر بودن 2 عنصر ترتیبی که عناصر در آرایه ورودی دارن در آرایه خروجی حفظ نمیشه )
برای stable شدن الگوریتم بالا نیاز به یکم تغیرات داریم که در ادامه توضیح میدم .