Overview
Bucket Sort is a comparison-based sorting algorithm that distributes elements of an array into several buckets. Each bucket is then sorted individually, either using another sorting algorithm or by recursively applying the bucket sort. After sorting, the elements are concatenated to form the final sorted array.
Key Characteristics
- Time Complexity: Average case O(n + k), where n is the number of elements and k is the number of buckets.
- Space Complexity: O(n + k), where k is the number of buckets.
- Stability: Depends on the sorting algorithm used within the buckets.
- Algorithm Type: Non-comparison-based, distribution sorting.
How Bucket Sort Works
- Divide into Buckets:
- Create several empty buckets.
- Distribute the elements of the array into buckets based on a specific range or condition.
- Sort Each Bucket:
- Sort the elements within each bucket using a suitable sorting algorithm (e.g., Insertion Sort).
- Concatenate Buckets:
- Concatenate all sorted buckets to get the final sorted array.
Steps and Example
Consider the following unsorted array:
[0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]Step 1: Divide into Buckets
- Assuming the elements are uniformly distributed in the range [0, 1), we divide the array into 5 buckets.
Bucket 0: [0.23, 0.25, 0.32]
Bucket 1: [0.42]
Bucket 2: [0.47]
Bucket 3: [0.51, 0.52]
Bucket 4: []Step 2: Sort Each Bucket
- Sort the elements in each bucket.
Bucket 0: [0.23, 0.25, 0.32] (already sorted)
Bucket 1: [0.42] (already sorted)
Bucket 2: [0.47] (already sorted)
Bucket 3: [0.51, 0.52] (already sorted)Step 3: Concatenate Buckets
- Concatenate the sorted buckets to get the final sorted array.
Final sorted array: [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]