الگوریتم مرتب‌سازی شمارشی (Counting Sort)
الگوریتم مرتب سازی شمارشی (Counting Sort)، یک تکنیک مرتب سازی مبتنی بر کلیدهای بین یک رنج خاص است. در این الگوریتم برخلاف الگوریتم هایی مثل Merge Sort که مبتنی بر مقایسه هستند، برای مرتب سازی از تکنیک شمارش عناصر آرایه استفاده می کند.
برای درک بهتر به مثال زیر توجه کنید:
For simplicity, consider the data in the range 0 to 9. Input data: 1, 4, 1, 2, 7, 5, 2 1) Take a count array to store the count of each unique object. Index: 0 1 2 3 4 5 6 7 8 9 Count: 0 2 2 0 1 1 0 1 0 0 2) Modify the count array such that each element at each index stores the sum of previous counts. Index: 0 1 2 3 4 5 6 7 8 9 Count: 0 2 4 4 5 6 6 7 7 7 The modified count array indicates the position of each object in the output sequence. 3) Output each object from the input sequence followed by decreasing its count by 1. Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2. Put data 1 at index 2 in output. Decrease count by 1 to place next data 1 at an index 1 smaller than this index.
پیاده سازی الگوریتم Counting Sort
در زیر می توانید نحوه پیاده سازی الگوریتم مرتب سازی شمارشی در زبان برنامه نویسی سی پلاس پلاس را مشاهده کنید:
// C++ Program for counting sort
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
#define RANGE 255
// The main function that sort
// the given string arr[] in
// alphabatical order
void countSort(char arr[])
{
// The output character array
// that will have sorted arr
char output[strlen(arr)];
// Create a count array to store count of inidividul
// characters and initialize count array as 0
int count[RANGE + 1], i;
memset(count, 0, sizeof(count));
// Store count of each character
for(i = 0; arr[i]; ++i)
++count[arr[i]];
// Change count[i] so that count[i] now contains actual
// position of this character in output array
for (i = 1; i <= RANGE; ++i)
count[i] += count[i-1];
// Build the output character array
for (i = 0; arr[i]; ++i)
{
output[count[arr[i]]-1] = arr[i];
--count[arr[i]];
}
/*
For Stable algorithm
for (i = sizeof(arr)-1; i>=0; --i)
{
output[count[arr[i]]-1] = arr[i];
--count[arr[i]];
}
For Logic : See implementation
*/
// Copy the output array to arr, so that arr now
// contains sorted characters
for (i = 0; arr[i]; ++i)
arr[i] = output[i];
}
// Driver code
int main()
{
char arr[] = "CFGBCAFygbG";
countSort(arr);
cout<< "Sorted character array is " << arr;
return 0;
}
امتحان کنید
خروجی کد فوق:
Sorted character array is ABCCFFGGbgy
نکات
- پیچیدگی زمانی الگوریتم برابر است با O(n+k) که در آن n تعداد عناصر آرایه ورودی و k رنج ورودی است.
- پیچیدگی فضایی برابر است با O(n+k).
مشکلی که پیاده سازی بالا دارد این است که اگر آرایه ورودی شامل مقادیر منفی باشد، نمی توانیم آن را مرتب کنیم. چون هیچ اندیسی برای اعداد منفی وجود ندارد. برای حل این مشکل می توانید آن را به شکل زیر پیاده سازی کنید.
//Counting sort which takes negative numbers as well
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void countSort(vector <int>& arr)
{
int max = *max_element(arr.begin(), arr.end());
int min = *min_element(arr.begin(), arr.end());
int range = max - min + 1;
vector<int> count(range), output(arr.size());
for(int i = 0; i < arr.size(); i++)
count[arr[i]-min]++;
for(int i = 1; i < count.size(); i++)
count[i] += count[i-1];
for(int i = arr.size()-1; i >= 0; i--)
{
output[ count[arr[i]-min] -1 ] = arr[i];
count[arr[i]-min]--;
}
for(int i=0; i < arr.size(); i++)
arr[i] = output[i];
}
void printArray(vector <int> & arr)
{
for (int i=0; i < arr.size(); i++)
cout << arr[i] << " ";
cout << "\n";
}
int main()
{
vector<int> arr = {-5, -10, 0, -3, 8, 5, -1, 10};
countSort (arr);
printArray (arr);
return 0;
}
امتحان کنید
خروجی:
-10 -5 -3 -1 0 5 8 10
نوشته الگوریتم مرتب سازی شمارشی (Counting Sort) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.
