.

# Bucket Sort Algorithm Assignment Help

- Bucket sort assume that the input is produced with a random process and drawn from a uniform distribution.
- In other words the elements are distributed uniformly and independently over the interval [0, 1].
- Bucket sort divides the interval [0, 1] into n equal sized subintervals or buckets. Then distributes the n inputs into these buckets.
- After that the elements of each bucket are sorted using a sorting algorithm generally using insertion o r quick sort.
- Finally the buckets are concatenated together in order.
- Consider that the input is an n-elements array A and each element A[i] in the array satisfies the 0 <= A [I] > 1.

## Bucket Sort Algorithm:

```
Bucket-Sort(A)
```

1. Let B[0….n-1] be a new array

2. n=length [A]

3. for i-0 to n-1

4. make b[i] an empty list

5. For i=1 to n

6. do insert A[i] into list B[!nA[1]]

7. For i=0 to n-1

8. do sort list B[i] with Insertion-Sort

9. Concatenate lists B[0], B[1],…..,B[n-1] together in order

### For Example:

Consider sorting a list of 10 numbers considered to be between 0 and 2, not including 2 it. Therefore, every bucket will store values in a range associated with 2/10 = .2 particularly, we have the following list:

Bucket | Range of Values | Bucket | Range of Values |
---|---|---|---|

0 | [0, .2] | 5 | [1, 1.2] |

1 | [.2, .4] | 6 | [1.2, 1.4] |

2 | [.4, .6] | 7 | [1.4, 1.6] |

3 | [.6, .8] | 8 | [1.6, 1.8] |

4 | [.8, 1] | 9 | [1.8, 2] |

Consider sorting the following list: 1.3, 0.7, 0.1, 1.8, 1.1, 1.0, 0.5, 1.7, 0.3, and 1.5. Consider that it's not essential for that input range to start at 0. As long as you have a lower and upper bound with regard to input, the bucket sort algorithm could be modified.

.