CSE2202-Algorithm-Design-and-Analysis/sort_Bucket.cpp at main · alamgir-ahosain/CSE2202-Algorithm-Design-and-Analysis · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void insertion(vector<float> &v)
{

    int n = v.size();
    for (int i = 1; i < n; i++)
    {

        int hole = i;
        int val = v[hole];
        while (hole > 0 && v[hole - 1] > val)
        {
            v[hole] = v[hole - 1];
            hole--;
        }
        v[hole] = val;
    }
}
// Function to sort arr[] of
// size n using bucket sort
void bucketSort(float arr[], int n)
{

    // 1) Create n empty buckets
    vector<float> bucket[n];

    // 2) Put array elements
    // in different buckets
    for (int i = 0; i < n; i++)
    {

        // Index in bucket
        int bi = n * arr[i];
        bucket[bi].push_back(arr[i]);
    }

    // 3) Sort individual buckets
    for (int i = 0; i < n; i++)
    {
        // sort(b[i].begin(), b[i].end());
        insertion(bucket[i]);
    }

    // 4) Concatenate all buckets into arr[]
    int index = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < bucket[i].size(); j++)
            arr[index++] = bucket[i][j];
}

// Driver program to test above function
int main()
{
    float arr[] = {0.232, 0.565, 0.656, 0.1234, 0.665, 0.3434};
    int n = sizeof(arr) / sizeof(arr[0]);
    bucketSort(arr, n);

    cout << "Sorted array is \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}
/*

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// Function to sort arr[] of
// size n using bucket sort
void bucketSort(float arr[], int n)
{

    //   1-- Create n empty buckets
    vector<float> b[n];

    float mini = arr[0];
    float maxi = arr[0];
    for (int i = 0; i < n; i++)
    {
        mini = min(mini, arr[i]);
        maxi = max(maxi, arr[i]);
    }

    float range = (maxi - mini) / n;
    // 2-- Put array elements in different buckets
    for (int i = 0; i < n; i++)
    {

        // Index in bucket
        int index = (arr[i] - mini) / range;
        float diff = (arr[i] - mini) / range - index;

        if (diff == 0 && arr[i] != mini)
            b[index - 1].push_back(arr[i]);
        else
            b[index].push_back(arr[i]);
    }

    // 3-- Sort individual buckets
    for (int i = 0; i < n; i++)
        sort(b[i].begin(), b[i].end());

    // 4-- Concatenate all buckets into arr[]
    int index = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < b[i].size(); j++)
            arr[index++] = b[i][j];
}


int main()
{
    float arr[] = {2.232, 1.565, 0.656, 0.1234, 0.665, 0.3434};
    int n = sizeof(arr) / sizeof(arr[0]);
    bucketSort(arr, n);

    cout << "Sorted array is \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}
 */