Golang Bucket Sort
last modified March 9, 2025
This tutorial dives into the bucket sort algorithm in Golang. We'll explore sorting numbers and text in ascending and descending order, and compare it with quick sort using benchmarks.
An algorithm is a structured set of steps to solve a problem or complete a task. It's a cornerstone of programming and computer science.
Sorting organizes data into a specific sequence, like ascending or descending. It's vital for efficient data handling and analysis in programs.
Common Sorting Algorithms
Here are some popular sorting algorithms:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Bucket Sort
Bucket Sort Algorithm
Bucket sort is a distribution-based sorting method. It divides elements into “buckets,” sorts each bucket individually, and then combines them. It shines when data is evenly spread across a range.
Unlike comparison-based sorts, it relies on distributing data, making it fast for uniform distributions but less effective otherwise.
Bucket Sort Example: Numeric Data
Here's a Golang implementation of bucket sort for numbers in ascending order.
package main
import (
"fmt"
"sort"
)
func bucketSort(arr []float64) []float64 {
if len(arr) == 0 {
return arr
}
maxVal := arr[0]
for _, val := range arr {
if val > maxVal {
maxVal = val
}
}
bucketSize := maxVal / float64(len(arr))
buckets := make([][]float64, len(arr))
for i := range buckets {
buckets[i] = []float64{}
}
for _, num := range arr {
idx := int(num / bucketSize)
if idx >= len(arr) {
idx = len(arr) - 1
}
buckets[idx] = append(buckets[idx], num)
}
for i := range buckets {
sort.Float64s(buckets[i])
}
result := []float64{}
for _, bucket := range buckets {
result = append(result, bucket...)
}
return result
}
func main() {
arr := []float64{0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51}
sorted := bucketSort(arr)
fmt.Println("Sorted array:", sorted)
}
This sorts a slice of floating-point numbers using bucket sort. It uses Go's
sort.Float64s to sort each bucket.
$ go run bucket_sort_numeric.go Sorted array: [0.32 0.33 0.37 0.42 0.47 0.51 0.52]
Bucket Sort Example: Textual Data
Here's an example sorting strings by length in descending order using bucket sort.
package main
import (
"fmt"
"sort"
)
func bucketSortTextual(arr []string) []string {
if len(arr) == 0 {
return arr
}
maxLen := 0
for _, s := range arr {
if len(s) > maxLen {
maxLen = len(s)
}
}
buckets := make([][]string, maxLen+1)
for i := range buckets {
buckets[i] = []string{}
}
for _, s := range arr {
buckets[len(s)] = append(buckets[len(s)], s)
}
for i := range buckets {
sort.Sort(sort.Reverse(sort.StringSlice(buckets[i])))
}
result := []string{}
for i := len(buckets) - 1; i >= 0; i-- {
result = append(result, buckets[i]...)
}
return result
}
func main() {
arr := []string{"apple", "banana", "kiwi", "mango", "pear"}
sorted := bucketSortTextual(arr)
fmt.Println("Sorted array:", sorted)
}
This sorts strings by length in descending order, with alphabetical reverse
order within each bucket using sort.Reverse.
$ go run bucket_sort_textual.go Sorted array: [banana mango apple pear kiwi]
Comparing Bucket Sort with Quick Sort
Bucket sort excels with uniformly distributed data, running in O(n + k) time where k is the number of buckets. Quick sort, averaging O(n log n), is more versatile for general cases.
Benchmark Example
This compares bucket sort and quick sort performance on a large dataset.
package main
import (
"fmt"
"math/rand"
"sort"
"time"
)
func bucketSort(arr []float64) []float64 {
if len(arr) == 0 {
return arr
}
maxVal := arr[0]
for _, val := range arr {
if val > maxVal {
maxVal = val
}
}
bucketSize := maxVal / float64(len(arr))
buckets := make([][]float64, len(arr))
for i := range buckets {
buckets[i] = []float64{}
}
for _, num := range arr {
idx := int(num / bucketSize)
if idx >= len(arr) {
idx = len(arr) - 1
}
buckets[idx] = append(buckets[idx], num)
}
for i := range buckets {
sort.Float64s(buckets[i])
}
result := []float64{}
for _, bucket := range buckets {
result = append(result, bucket...)
}
return result
}
func quickSort(arr []float64) []float64 {
if len(arr) <= 1 {
return arr
}
pivot := arr[len(arr)/2]
left, middle, right := []float64{}, []float64{}, []float64{}
for _, x := range arr {
if x < pivot {
left = append(left, x)
} else if x == pivot {
middle = append(middle, x)
} else {
right = append(right, x)
}
}
return append(append(quickSort(left), middle...), quickSort(right)...)
}
func main() {
rand.Seed(time.Now().UnixNano())
arr := make([]float64, 10000)
for i := range arr {
arr[i] = rand.Float64() * 1000
}
start := time.Now()
bucketSort(append([]float64{}, arr...))
fmt.Printf("Bucket Sort Time: %.6f seconds\n", time.Since(start).Seconds())
start = time.Now()
quickSort(append([]float64{}, arr...))
fmt.Printf("Quick Sort Time: %.6f seconds\n", time.Since(start).Seconds())
}
This benchmarks both algorithms on 10,000 random floats. Bucket sort may edge out on uniform data, but quick sort is more consistent overall.
Source
We've covered bucket sort in Golang and compared it with quick sort. It's great for uniform data, while quick sort is a robust all-purpose choice.
Author
List all Golang tutorials.