Trong kỹ thuật Sắp xếp nhóm, các mục dữ liệu được phân phối thành một nhóm nhóm. Mỗi nhóm có thể chứa loại dữ liệu tương tự. Sau khi phân phối, mỗi nhóm được sắp xếp bằng cách sử dụng một thuật toán sắp xếp khác. Sau đó, tất cả các phần tử được tập hợp vào danh sách chính để có được biểu mẫu được sắp xếp.
Mức độ phức tạp của Kỹ thuật sắp xếp theo nhóm
-
Độ phức tạp về thời gian:O (n + k) cho trường hợp tốt nhất và trường hợp trung bình và O (n2) cho trường hợp xấu nhất.
-
Độ phức tạp về không gian:O (nk) cho trường hợp xấu nhất
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 Output − Array after Sorting: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79
Thuật toán
bucketSort (mảng, kích thước)
Đầu vào :Một mảng dữ liệu và tổng số trong mảng
Đầu ra :Mảng được sắp xếp
Begin
for i := 0 to size-1 do
insert array[i] into the 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 Mã mẫu
#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++) { //put elements into different buckets
bucket[int(size*array[i])].push_back(array[i]);
}
for(int i = 0; i<size; i++) {
sort(bucket[i].begin(), bucket[i].end()); //sort individual vectors
}
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]; //create an array with given number of elements
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);
} Đầu ra
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