Bucket Sort Algorithm

Bucket Sort is a sorting algorithm that works by:

Dividing the input array into several “buckets” (groups) and then sorting each bucket individually, usually using another sorting algorithm (like Insertion Sort). After sorting all the buckets, they are combined to form the final sorted array.

It is efficient when the input is uniformly distributed over a range.

How Bucket Sort Works (Step-by-Step)

1. Create Buckets:
   Create empty buckets (lists or arrays).
2. Distribute the Elements:
   Place each element from the input array into a bucket based on its value.
3. Sort Each Bucket:
   Sort each bucket individually (often using Insertion Sort or any other sorting algorithm).
4. Concatenate Buckets:
   Combine all buckets back into the original array in order.

Example:

Input: [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]

Step 1: Create 10 buckets for range [0,1)

Empty buckets:
[[], [], [], [], [], [], [], [], [], []]

Step 2: Place numbers into buckets

• Based on floor (value × 10):
• 42 → bucket [4]
• 32 → bucket [3]
• 23 → bucket [2]
• 52 → bucket [5]
• 25 → bucket [2]
• 47 → bucket [4]
• 51 → bucket [5]

   Now:

• bucket [2] = [0.23, 0.25]
• bucket [3] = [0.32]
• bucket [4] = [0.42, 0.47]
• bucket [5] = [0.52, 0.51]

Step 3: Sort each bucket

• bucket [2] → [0.23, 0.25]
• bucket [3] → [0.32]
• bucket [4] → [0.42, 0.47]
• bucket [5] → [0.51, 0.52]

Step 4: Combine all buckets

Sorted array: [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]

   Bucket sort python code:

function bucketSort(arr):

    n = len(arr)

    buckets = [[] for i in range(n)]

    for i in range(n):

        index = int(n * arr[i])

        buckets[index].append(arr[i])

    for bucket in buckets:

        insertionSort(bucket)

    return concatenate(buckets)

 Time Complexity

• n = number of elements
• k = number of buckets