SHOW:
|
|
- or go back to the newest paste.
1 | // C++ program to sort an array using bucket sort | |
2 | #include <algorithm> | |
3 | #include <iostream> | |
4 | #include <vector> | |
5 | using namespace std; | |
6 | ||
7 | void sortowanie_kubelkowe(float tab[], int n) | |
8 | - | // Function to sort arr[] of size n using bucket sort |
8 | + | |
9 | - | void bucketSort(float arr[], int n) |
9 | + | // 1) |
10 | vector<float> kub[n]; | |
11 | - | // 1) Create n empty buckets |
11 | + | |
12 | - | vector<float> b[n]; |
12 | + | // 2) |
13 | for (int i = 0; i < n; i++) { | |
14 | - | // 2) Put array elements in different buckets |
14 | + | int i_kub = n * tab[i]; |
15 | kub[i_kub].push_back(tab[i]); | |
16 | - | int bi = n * arr[i]; // Index in bucket |
16 | + | |
17 | - | b[bi].push_back(arr[i]); |
17 | + | |
18 | // 3) | |
19 | for (int i = 0; i < n; i++) | |
20 | - | // 3) Sort individual buckets |
20 | + | sort(kub[i].begin(), kub[i].end()); |
21 | ||
22 | - | sort(b[i].begin(), b[i].end()); |
22 | + | // 4) |
23 | int index = 0; | |
24 | - | // 4) Concatenate all buckets into arr[] |
24 | + | |
25 | for (int j = 0; j < kub[i].size(); j++) | |
26 | tab[index++] = kub[i][j]; | |
27 | - | for (int j = 0; j < b[i].size(); j++) |
27 | + | |
28 | - | arr[index++] = b[i][j]; |
28 | + | |
29 | int main() | |
30 | { | |
31 | - | /* Driver program to test above function */ |
31 | + | float tab[] = { 0.257, 0.1064, 0.598, 0.9876, 0.123, 0.456, 0.789 }; |
32 | int n = sizeof(tab) / sizeof(tab[0]); | |
33 | sortowanie_kubelkowe(tab, n); | |
34 | - | float arr[] = { 0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434 }; |
34 | + | |
35 | - | int n = sizeof(arr) / sizeof(arr[0]); |
35 | + | cout << "Posortowana tablica: \n"; |
36 | - | bucketSort(arr, n); |
36 | + | |
37 | cout << tab[i] << " "; | |
38 | - | cout << "Sorted array is \n"; |
38 | + | |
39 | } | |
40 | - | cout << arr[i] << " "; |
40 | + |