# Bucket Sort Analysis

Bucket Sort is a sorting algorithm that works by dividing an array into a set of buckets, where each bucket is sorted individually using another sorting algorithm. It is a distribution-based sorting algorithm, which means that it uses the range of input values to divide the input into smaller subarrays or buckets. Bucket Sort is particularly useful when the input is uniformly distributed over a range of values.

## How Algorithm of Bucket Sort works?

The algorithm of Bucket Sort is as follows:

1. Create an empty array of buckets with the same size as the input array.
2. Scatter: Iterate through the input array, and for each element, determine which bucket it belongs to and add it to that bucket.
3. Sort each bucket using a comparison-based sorting algorithm like quicksort, mergesort, or heapsort. Alternatively, we can use another sorting algorithm recursively if the bucket size is greater than some threshold value.
4. Gather: Iterate through the buckets in order and concatenate the sorted elements into a single output array.

Here is the pseudocode for Bucket Sort:

``````bucketSort(arr[], n, k):
Create n empty buckets
for i = 0 to (n - 1):
Insert arr[i] into bucket[n * arr[i]]
for i = 0 to (n - 1):
Sort bucket[i] using insertion sort (or any other sorting algorithm)
Concatenate all sorted buckets into arr[]
``````

In this pseudocode, `arr` is the input array of size `n`, and `k` is the number of buckets (which can be chosen based on the distribution of the input values). The `Insert` function determines which bucket a given element should be placed in, and the `Sort` function sorts each bucket using an appropriate algorithm. The final step concatenates all the sorted buckets into the output array.

### Example Code

Here’s a basic C++ program for Bucket Sort:

```#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void bucketSort(float arr[], int n)
{
vector<float> buckets[n];

for (int i = 0; i < n; i++)
{
int bucketIndex = n * arr[i];
buckets[bucketIndex].push_back(arr[i]);
}

for (int i = 0; i < n; i++)
{
sort(buckets[i].begin(), buckets[i].end());
}

int index = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < buckets[i].size(); j++)
{
arr[index++] = buckets[i][j];
}
}
}

int main()
{
float arr[] = {0.23, 0.10, 0.46, 0.91, 0.55, 0.42, 0.86, 0.34, 0.29, 0.68};
int n = sizeof(arr) / sizeof(arr);

cout << "Before sorting: ";
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;

bucketSort(arr, n);

cout << "After sorting: ";
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;

return 0;
}
```

The above program will output:

``````Before sorting: 0.23 0.1 0.46 0.91 0.55 0.42 0.86 0.34 0.29 0.68
After sorting: 0.1 0.23 0.29 0.34 0.42 0.46 0.55 0.68 0.86 0.91 ``````

In this program, the `bucketSort` function takes an array of floating-point numbers and its size as input. It creates an array of `n` vectors to hold the values in the input array. Then, it calculates the index of each value in the input array using `n * arr[i]`, which maps each value to a bucket index based on its fractional part. Each value is then inserted into the corresponding bucket using the `push_back` function.

Next, the function sorts each bucket using the `sort` function from the `<algorithm>` library. Finally, it copies the values from each bucket back into the original array in order, resulting in a sorted array.

The `main` function simply creates an example array, calls the `bucketSort` function, and prints the sorted array.

## Complexity Analysis of Bucket Sort

The time complexity of Bucket Sort depends on the algorithm used to sort the elements in the individual buckets.

If the bucket sort algorithm used is a comparison-based sorting algorithm like quicksort or mergesort, then the time complexity of Bucket Sort will be O(nlogn).

If the elements in the buckets are sorted using an efficient non-comparison sorting algorithm like counting sort or radix sort, then the time complexity of Bucket Sort can be O(n+k), where n is the number of elements and k is the range of values.

In the worst case, if all the elements are placed in a single bucket, the time complexity would be O(n^2). However, this is a rare scenario that can be avoided by choosing an appropriate number of buckets.

The space complexity of Bucket Sort is O(n+k), where n is the number of elements and k is the range of values. This is because we need to create k buckets to hold the elements, and each bucket may contain multiple elements.

## Where is the Bucket Sort algorithm used?

Bucket Sort is used when the input data is uniformly distributed over a range. It is particularly useful when the range of the input is known in advance, as it can improve the overall time complexity of the sorting algorithm. Bucket Sort is often used in parallel processing and distributed systems, as it can be easily parallelized due to the independent nature of the buckets. It is also used in digital signal processing and computer graphics.

1. It is faster than many other sorting algorithms, especially when the input data is uniformly distributed over a range.
2. Bucket Sort is a stable sorting algorithm, which means that it maintains the relative order of equal elements in the sorted array.
3. It is relatively easy to implement and can be used as a subroutine in other algorithms.
4. It is efficient for sorting large data sets that have a uniform distribution.