Scribd
Upload
7 views4 pages

Bucket Sort

Bucket Sort is an efficient sorting algorithm that distributes elements into buckets, sorts each bucket, and then concatenates the results. It has a best and average time complexity of O(n) when elements are uniformly distributed, but can degrade to O(n²) in the worst case if all elements fall into a single bucket. The space complexity is O(n + k), where n is the number of elements and k is the number of buckets.

Uploaded by

Pranav
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views4 pages

Bucket Sort

Bucket Sort is an efficient sorting algorithm that distributes elements into buckets, sorts each bucket, and then concatenates the results. It has a best and average time complexity of O(n) when elements are uniformly distributed, but can degrade to O(n²) in the worst case if all elements fall into a single bucket. The space complexity is O(n + k), where n is the number of elements and k is the number of buckets.

Uploaded by

Pranav
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Bucket Sort

Input A = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12] n = 8 buckets Range = [0,1)

Bucket Sort — Pseudocode + Dry Run (Side by Side)

Pseudocode Step Dry Run on Example


B0: [] B1: [] B2: [] B3: [] B4: [] B5: [] B6: [] B7:
Create B[0…7] empty buckets
[]
For each A[i], compute index =
floor(8 × A[i])
A[0] = 0.78 → index =
B6: [0.78]
floor(8×0.78)=6
A[1] = 0.17 → index =
B1: [0.17]
floor(8×0.17)=1
A[2] = 0.39 → index =
B3: [0.39]
floor(3.12)=3
A[3] = 0.26 → index =
B2: [0.26]
floor(2.08)=2
A[4] = 0.72 → index =
B5: [0.72]
floor(5.76)=5
A[5] = 0.94 → index =
B7: [0.94]
floor(7.52)=7
A[6] = 0.21 → index =
B1: [0.17, 0.21]
floor(1.68)=1
A[7] = 0.12 → index =
B0: [0.12]
floor(0.96)=0

Buckets After Distribution

B0: [0.12] B1: [0.17, 0.21] B2: [0.26] B3: [0.39] B4: [] B5: [0.72] B6: [0.78] B7: [0.94]

Pseudocode Step Dry Run


Sort each bucket B1 becomes [0.17, 0.21] (already sorted)
using insertion sort All other buckets have ≤1 element → already sorted

Pseudocode Step Dry Run (Concatenation)


Traverse buckets from 0 to 7 and copy A = [0.12, 0.17, 0.21, 0.26, 0.39, 0.72,
back into A 0.78, 0.94]
Final Sorted Output

0.12, 0.17, 0.21, 0.26, 0.39, 0.72, 0.78, 0.94

Why This Was Fast

• Elements were uniformly distributed • Buckets had small sizes • Insertion sort cost per
bucket was tiny

Total work ≈ O(n)

Bucket Sort — Time & Space Complexity

Idea (1 line intuition)

Distribute elements into buckets, sort each bucket individually, then concatenate.

Time Complexity
Let:

n = number of elements
k = number of buckets

Best Case:

O(n + k)

Happens when:

Data is uniformly distributed


Each bucket has ~ n/k elements
Sorting inside buckets is very cheap (e.g., small size)

If insertion sort is used inside buckets, and buckets are evenly filled:

[ T(n) = O(n) + k O((n/k)^2)]

If k ≈ n → each bucket has ~1 element → total becomes:

[ O(n)]

So best case: O(n)

Average Case:

O(n + k)

When:
Input is reasonably uniformly distributed
Buckets are balanced

If k = n:

[ O(n)]

So average case is typically linear.

Worst Case:

O(n²)

Happens when:

All elements fall into one bucket


That bucket is sorted using insertion sort

Then it degenerates into:

[ O(n^2)]

So worst case: O(n²)

Space Complexity
We need:

Buckets storage → O(n)


Auxiliary structure → O(k)

So total:

[ O(n + k)]

If k ≈ n → space becomes:

O(n)

Summary Table
Case Time Complexity
Best O(n)
Average O(n)
Worst O(n²)
Space O(n + k)
When is Bucket Sort Ideal?
✔ Numbers uniformly distributed ✔ Floating point numbers in range [0,1) ✔ When linear
time is desirable

If you’d like, I can now:

Compare Bucket vs Radix vs Counting


Show a dry run
Derive complexity mathematically from expectation
Or give pseudocode + proof intuition

You might also like