বাকেট সোর্টিং টেকনিকে (Bucket Sort), ডেটা আইটেমগুলো বাকেটের একটি সেটে ডিস্ট্রিবিউট করা হয়। প্রতিটি বাকেট একই ধরনের ডেটা ধারণ করতে পারে। ডিস্ট্রিবিউট করার পর, প্রতিটি বাকেট অন্য একটি সোর্টিং অ্যালগরিদম ব্যবহার করে সর্ট করা হয়। তারপর সব এলিমেন্ট মেন লিস্টে গ্যাথার করা হয় সর্টেড ফর্ম পেতে।
বাকেট সর্ট টেকনিকের জটিলতা
সময় জটিলতা: বেস্ট এবং গড় কেসে O(n + k), ওasst কেসে O(n²)
স্পেস জটিলতা: ওasst কেসে O(nk)
ইনপুট − একটি আনসর্টেড ডেটা লিস্ট: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69 আউটপুট − সর্টিংয়ের পর অ্যারে: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79
অ্যালগরিদম
bucketSort(array, size)
ইনপুট: একটি ডেটা অ্যারে, এবং অ্যারেতে মোট সংখ্যা
আউটপুট: সর্টেড অ্যারে
শুরু
i := 0 থেকে size-1 পর্যন্ত
array[i] কে বাকেট ইনডেক্স (size * array[i])-এ ইনসার্ট করুন
শেষ
i := 0 থেকে size-1 পর্যন্ত
bucket[i] সর্ট করুন
inished
i := 0 থেকে size-1 পর্যন্ত
bucket[i]-এর আইটেমগুলো গ্যাথার করে অ্যারেতে রাখুন
inished
শেষ
উদাহরণ কোড
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void display(float *array, int size) {
for(int i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
void bucketSort(float *array, int size) {
vector<float> bucket[size];
for(int i = 0; i < size; i++) {
bucket[int(size*array[i])].push_back(array[i]);
}
for(int i = 0; i < size; i++) {
sort(bucket[i].begin(), bucket[i].end());
}
int index = 0;
for(int i = 0; i < size; i++) {
while(!bucket[i].empty()) {
array[index++] = *(bucket[i].begin());
bucket[i].erase(bucket[i].begin());
}
}
}
int main() {
int n;
cout << "এলিমেন্টের সংখ্যা দিন: ";
cin >> n;
float arr[n];
cout << "এলিমেন্টগুলো দিন:" << endl;
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "সর্টিংয়ের আগে অ্যারে: ";
display(arr, n);
bucketSort(arr, n);
cout << "সর্টিংয়ের পর অ্যারে: ";
display(arr, n);
}
আউটপুট
এলিমেন্টের সংখ্যা দিন: 10 এলিমেন্টগুলো দিন: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69 সর্টিংয়ের আগে অ্যারে: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69 সর্টিংয়ের পর অ্যারে: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79
