কিছু ছোট নম্বর লিনিয়ার টাইমে সর্ট করতে আমরা কাউন্টিং সোর্ট টেকনিক ব্যবহার করতে পারি।
কাউন্টিং সোর্ট একটি স্টেবল সোর্টিং টেকনিক, যা ছোট নম্বর কী হিসেবে ব্যবহার করে অবজেক্ট সর্ট করতে ব্যবহৃত হয়। এটি সেই কী ভ্যালুর সংখ্যা গণনা করে যাদের কী ভ্যালু একই। এই সোর্টিং টেকনিক তখন ইফিশিয়েন্ট যখন বিভিন্ন কীর মধ্যে পার্থক্য ঠিক তেমন বড় নয়, অন্যথায় এটি স্পেস কমপ্লেক্সিটি বেড়াতে পারে।
কাউন্টিং সোর্ট টেকনিকের কমপ্লেক্সিটি
টাইম কমপ্লেক্সিটি: 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 = অ্যারে থেকে ম্যাক্সিমাম এলিমেন্ট বের করুন।
count অ্যারে ডিফাইন করুন আকার [max+1]
for i := 0 to max do
count[i] = 0 // কাউন্ট অ্যারেতে সব এলিমেন্ট ০ সেট করুন
লুপ শেষ
for i := 1 to size do
অ্যারেতে পাওয়া যే প্রতিটি নম্বরের কাউন্ট বাড়ান
লুপ শেষ
for i := 1 to max do
count[i] = count[i] + count[i + 1] // কিউমুলেটিভ ফ্রিকোয়েন্সি বের করুন
লুপ শেষ
for i := size to 1 ১ করে ডিক্রিজ করে, করুন
আউটপুট অ্যারেতে নম্বরটি স্টোর করুন
count[i] ডিক্রিজ করুন
লুপ শেষ
আউটপুট অ্যারে রিটার্ন করুন
শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
void counting_sort(int array[], int n) {
int i, j;
int count[n];
for (i = 0; i < n; i++)
count[i] = 0;
for (i = 0; i < n; i++)
(count[array[i]])++;
for (i = 0, j = 0; i < n; i++)
for (; count[i] > 0; (count[i])--)
array[j++] = i;
}
int main() {
int array[100], i, num;
cout << "Enter the size of array : ";
cin >> num;
cout << "Enter the " << num << " elements to be sorted:" << endl;
for (i = 0; i < num; i++)
cin >> array[i];
cout << "\nThe array of elements before sorting : " <
আউটপুট
Enter the size of array : 8
Enter the 8 elements to be sorted: 54 89 23 20 18 88 65 31
The array of elements before sorting : 54 89 23 20 18 88 65 31
The array of elements after sorting : 54 89 23 20 18 88 65 31
