বাকেট সোর্ট-এ ডেটা আইটেমগুলো কিছু বাকেটে বিতরণ করা হয়। প্রতিটি বাকেটে একই ধরনের ডেটা থাকে। বিতরণের পর প্রতিটি বাকেটকে অন্য কোনো সোর্টিং অ্যালগরিদম দিয়ে সর্ট করা হয়। সবগুলো এলিমেন্ট মূল লিস্টে গ্যাদার করে সর্টেড ফর্ম পাওয়া যায়।
বাকেট সোর্টের জটিলতা
- টাইম কমপ্লেক্সিটি: বেস্ট/এভারেজ O(n + k), ওয়ার্স্ট O(n²)
- স্পেস কমপ্লেক্সিটি: ওয়ার্স্ট কেসে O(nk)
ইনপুট এবং আউটপুট
Input: A list of unsorted data: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Array before Sorting: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Output: Array after Sorting: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79
অ্যালগরিদম
bucketSort(array, size)
Input: ডেটার অ্যারে, মোট এলিমেন্ট
Output: সর্ট করা অ্যারে
Begin
for i := 0 to size-1 do
insert array[i] into bucket index (size * array[i])
done
for i := 0 to size-1 do
sort bucket[i]
done
for i := 0 to size-1 do
gather items of bucket[i] and put in array
done
End
C++ উদাহরণ
#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 << "Enter the number of elements: "; cin >> n;
float arr[n];
cout << "Enter elements:" << endl;
for(int i = 0; i < n; i++) cin >> arr[i];
cout << "Array before Sorting: "; display(arr, n);
bucketSort(arr, n);
cout << "Array after Sorting: "; display(arr, n);
}
আউটপুট
Enter the number of elements: 10
Enter elements: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Array before Sorting: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Array after Sorting: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79
