কাউন্টিং সোর্ট একটি স্ট্যাবল সোর্টিং টেকনিক যা ছোট সংখ্যার কি অনুযায়ী অবজেক্ট সর্ট করে। এটি প্রতিটি কি ভ্যালুর ফ্রিকোয়েন্সি কাউন্ট করে। এই টেকনিক তখন কার্যকর হয় যখন বিভিন্ন কির মধ্যে পার্থক্য বেশি না হয়, অন্যথায় স্পেস কমপ্লেক্সিটি বাড়ে।
কাউন্টিং সোর্টের জটিলতা
- টাইম কমপ্লেক্সিটি: O(n + r)
- স্পেস কমপ্লেক্সিটি: O(n + r)
ইনপুট এবং আউটপুট
Input: A list of unsorted data: 2 5 6 2 3 10 3 6 7 8
Output: Array before Sorting: 2 5 6 2 3 10 3 6 7 8
Array after Sorting: 2 2 3 3 5 6 6 7 8 10
অ্যালগরিদম
countingSort(array, size)
Input: ডেটার অ্যারে, মোট এলিমেন্ট
Output: সর্ট করা অ্যারে
Begin
max = array থেকে ম্যাক্সিমাম এলিমেন্ট
count অ্যারে সাইজ [max+1] ডিফাইন করুন
for i := 0 to max do count[i] = 0 done
for i := 1 to size do count[array[i]]++ done
for i := 1 to max do count[i] += count[i-1] done // কিউমুলেটিভ ফ্রিকোয়েন্সি
for i := size down to 1 do
output[count[array[i]]] = array[i]
count[array[i]]--
done
output অ্যারে রিটার্ন করুন
End
C++ উদাহরণ
#include <iostream>
#include <algorithm>
using namespace std;
void display(int *array, int size) {
for(int i = 1; i <= size; i++) cout << array[i] << " ";
cout << endl;
}
int getMax(int array[], int size) {
int max = array[1];
for(int i = 2; i <= size; i++) if(array[i] > max) max = array[i];
return max;
}
void countSort(int *array, int size) {
int output[size+1];
int max = getMax(array, size);
int count[max+1];
for(int i = 0; i <= max; i++) count[i] = 0;
for(int i = 1; i <= size; i++) count[array[i]]++;
for(int i = 1; i <= max; i++) count[i] += count[i-1];
for(int i = size; i >= 1; i--) {
output[count[array[i]]] = array[i];
count[array[i]]--;
}
for(int i = 1; i <= size; i++) array[i] = output[i];
}
int main() {
int n; cout << "Enter the number of elements: "; cin >> n;
int arr[n+1];
cout << "Enter elements:" << endl;
for(int i = 1; i <= n; i++) cin >> arr[i];
cout << "Array before Sorting: "; display(arr, n);
countSort(arr, n);
cout << "Array after Sorting: "; display(arr, n);
}
আউটপুট
Enter the number of elements: 10
Enter elements: 2 5 6 2 3 10 3 6 7 8
Array before Sorting: 2 5 6 2 3 10 3 6 7 8
Array after Sorting: 2 2 3 3 5 6 6 7 8 10
