কাউন্টিং সর্ট (Counting Sort) একটি স্টেবল সোর্টিং টেকনিক, যা ছোট সংখ্যা কি হিসেবে থাকা অবজেক্ট সর্ট করতে ব্যবহৃত হয়। এটি একই কি ভ্যালু 가진 কিয়ের সংখ্যা গণনা করে। এই সোর্টিং টেকনিক তখন কার্যকর হয় যখন বিভিন্ন কির পার্থক্য বেশি বড় নয়, অন্যথায় স্পেস জটিলতা বাড়তে পারে।
কাউন্টিং সর্ট টেকনিকের জটিলতা
সময় জটিলতা: O(n+r)
স্পেস জটিলতা: O(n+r)
ইনপুট − একটি আনসর্টেড ডেটা লিস্ট: 2 5 6 2 3 10 3 6 7 8
আউটপুট − সর্টিংয়ের পর অ্যারের অবস্থা: 2 2 3 3 5 6 6 7 8 10
অ্যালগরিদম
countingSort(array, size)
ইনপুট: একটি ডেটা অ্যারে, এবং অ্যারেতে মোট সংখ্যা
আউটপুট: সর্টেড অ্যারে
শুরু
max = অ্যারে থেকে সর্বোচ্চ এলিমেন্ট বের করুন
সাইজ [max+1] এর count অ্যারে ডিফাইন করুন
i := 0 থেকে max পর্যন্ত
count[i] = 0 // count অ্যারের সব এলিমেন্ট ০ করুন
শেষ
i := 1 থেকে size পর্যন্ত
অ্যারেতে যেসব সংখ্যা পাওয়া গেল, তাদের কাউন্ট বাড়ান
শেষ
i := 1 থেকে max পর্যন্ত
count[i] = count[i] + count[i-1] // কিউমুলেটিভ ফ্রিকোয়েন্সি বের করুন
শেষ
i := size থেকে ১ পর্যন্ত ১ করে কমিয়ে
আউটপুট অ্যারেতে সংখ্যা স্টোর করুন
count[i] কমান
শেষ
আউটপুট অ্যারে ফেরত দাও
শেষ
উদাহরণ কোড
#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]] -= 1;
}
for(int i = 1; i <= size; i++) {
array[i] = output[i];
}
}
int main() {
int n;
cout << "এলিমেন্টের সংখ্যা দিন: ";
cin >> n;
int arr[n+1];
cout << "এলিমেন্টগুলো দিন:" << endl;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
}
cout << "সর্টিংয়ের আগে অ্যারে: ";
display(arr, n);
countSort(arr, n);
cout << "সর্টিংয়ের পর অ্যারে: ";
display(arr, n);
}
আউটপুট
এলিমেন্টের সংখ্যা দিন: 10 এলিমেন্টগুলো দিন: 2 5 6 2 3 10 3 6 7 8 সর্টিংয়ের আগে অ্যারে: 2 5 6 2 3 10 3 6 7 8 সর্টিংয়ের পর অ্যারে: 2 2 3 3 5 6 6 7 8 10
