# 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] 7. For i=0 to n-1 8. do sort list B[i] with Insertion-Sort 9. Concatenate lists B, B,…..,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:

BucketRange of ValuesBucketRange 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.