Sorting is a fundamental concept in programming that helps organize data in a meaningful order. Whether you are building a leaderboard, managing financial data, or displaying results in a game, sorting ensures that information is presented clearly and efficiently. Among the many sorting algorithms available, Bucket Sort is a practical and efficient method, especially for datasets that are distributed over a known range.
with hands-on learning.
get the skills and confidence to land your next move.
Bucket Sort works by dividing the dataset into several groups called buckets. Each bucket contains numbers within a specific range, and the elements within each bucket are sorted individually. Once all buckets are sorted, their contents are combined to form a single sorted array. This makes Bucket Sort particularly useful for floating-point numbers between 0 and 1, or any data where values are evenly distributed. In this article, we will explore multiple Kotlin implementations of Bucket Sort, helping beginners understand its logic and apply it effectively.
Program 1: Basic Bucket Sort Using Lists
This program demonstrates the standard approach to Bucket Sort using Kotlin’s lists. The array is divided into buckets, each bucket is sorted using Kotlin’s built-in sort function, and finally, the sorted buckets are combined.
fun bucketSort(arr: DoubleArray, bucketSize: Int = 5) {
if (arr.isEmpty()) return
val minValue = arr.min()!!
val maxValue = arr.max()!!
val bucketCount = ((maxValue - minValue) / bucketSize).toInt() + 1
val buckets = Array(bucketCount) { mutableListOf<Double>() }
for (num in arr) {
val index = ((num - minValue) / bucketSize).toInt()
buckets[index].add(num)
}
for (bucket in buckets) {
bucket.sort()
}
var index = 0
for (bucket in buckets) {
for (num in bucket) {
arr[index++] = num
}
}
}
fun main() {
val numbers = doubleArrayOf(0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51)
println("Original Array: ${numbers.joinToString()}")
bucketSort(numbers)
println("Sorted Array: ${numbers.joinToString()}")
}This implementation divides the array based on value ranges. Each number is assigned to a bucket, the bucket is sorted, and then all buckets are combined. Beginners can see how breaking the problem into smaller parts simplifies sorting, making it easier to understand.
Program 2: Bucket Sort with Custom Sorting Function
Instead of relying on the built-in sort() function, this program uses Insertion Sort to organize elements within each bucket. This allows learners to understand how different sorting algorithms can work together.
fun insertionSort(bucket: MutableList<Double>) {
for (i in 1 until bucket.size) {
val key = bucket[i]
var j = i - 1
while (j >= 0 && bucket[j] > key) {
bucket[j + 1] = bucket[j]
j--
}
bucket[j + 1] = key
}
}
fun bucketSortCustom(arr: DoubleArray, bucketSize: Int = 5) {
if (arr.isEmpty()) return
val minValue = arr.min()!!
val maxValue = arr.max()!!
val bucketCount = ((maxValue - minValue) / bucketSize).toInt() + 1
val buckets = Array(bucketCount) { mutableListOf<Double>() }
for (num in arr) {
val index = ((num - minValue) / bucketSize).toInt()
buckets[index].add(num)
}
for (bucket in buckets) {
insertionSort(bucket)
}
var index = 0
for (bucket in buckets) {
for (num in bucket) {
arr[index++] = num
}
}
}
fun main() {
val numbers = doubleArrayOf(0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68)
println("Original Array: ${numbers.joinToString()}")
bucketSortCustom(numbers)
println("Sorted Array: ${numbers.joinToString()}")
}Here, Insertion Sort handles the sorting inside each bucket. This method is helpful for beginners who want to learn how algorithms can complement each other, giving a deeper understanding of sorting mechanics.
Program 3: Bucket Sort for Integers
Bucket Sort is not limited to floating-point numbers. This version demonstrates how to use it with integer arrays by adjusting the bucket range.
fun bucketSortIntegers(arr: IntArray, bucketSize: Int = 5) {
if (arr.isEmpty()) return
val minValue = arr.min()!!
val maxValue = arr.max()!!
val bucketCount = ((maxValue - minValue) / bucketSize) + 1
val buckets = Array(bucketCount) { mutableListOf<Int>() }
for (num in arr) {
val index = (num - minValue) / bucketSize
buckets[index].add(num)
}
var index = 0
for (bucket in buckets) {
bucket.sort()
for (num in bucket) {
arr[index++] = num
}
}
}
fun main() {
val numbers = intArrayOf(42, 32, 33, 52, 37, 47, 51)
println("Original Array: ${numbers.joinToString()}")
bucketSortIntegers(numbers)
println("Sorted Array: ${numbers.joinToString()}")
}By adjusting the bucket range, integers can be grouped and sorted efficiently. This example helps beginners see that Bucket Sort can work with different types of numerical data, not just decimals.
Program 4: Iterative Bucket Sort Using Kotlin Collections
This approach uses Kotlin’s collection framework fully and avoids recursion entirely. Each bucket is a list, and after sorting, the buckets are merged into a single sorted array.
fun bucketSortList(arr: MutableList<Double>, bucketSize: Int = 5) {
if (arr.isEmpty()) return
val minValue = arr.min()!!
val maxValue = arr.max()!!
val bucketCount = ((maxValue - minValue) / bucketSize).toInt() + 1
val buckets = Array(bucketCount) { mutableListOf<Double>() }
for (num in arr) {
val index = ((num - minValue) / bucketSize).toInt()
buckets[index].add(num)
}
for (bucket in buckets) {
bucket.sort()
}
arr.clear()
for (bucket in buckets) {
arr.addAll(bucket)
}
}
fun main() {
val numbers = mutableListOf(0.89, 0.45, 0.67, 0.23, 0.12, 0.78, 0.56)
println("Original List: $numbers")
bucketSortList(numbers)
println("Sorted List: $numbers")
}This version is beginner-friendly because it avoids complex recursion, uses Kotlin’s list features, and clearly separates each step: bucketing, sorting, and merging.
Program 5: Bucket Sort in Descending Order
Sometimes, instead of ascending order, we need the data sorted from largest to smallest. This program modifies the bucket merging step to achieve a descending order sort while keeping the rest of the algorithm unchanged.
fun bucketSortDescending(arr: DoubleArray, bucketSize: Int = 5) {
if (arr.isEmpty()) return
val minValue = arr.min()!!
val maxValue = arr.max()!!
val bucketCount = ((maxValue - minValue) / bucketSize).toInt() + 1
val buckets = Array(bucketCount) { mutableListOf<Double>() }
for (num in arr) {
val index = ((num - minValue) / bucketSize).toInt()
buckets[index].add(num)
}
for (bucket in buckets) {
bucket.sort()
}
var index = 0
for (i in buckets.size - 1 downTo 0) { // Start from last bucket
for (num in buckets[i].asReversed()) { // Reverse each bucket
arr[index++] = num
}
}
}
fun main() {
val numbers = doubleArrayOf(0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51)
println("Original Array: ${numbers.joinToString()}")
bucketSortDescending(numbers)
println("Sorted in Descending Order: ${numbers.joinToString()}")
}In this version, after sorting each bucket in ascending order, we merge the buckets starting from the last bucket and also reverse the contents of each bucket. This ensures that the largest numbers come first, giving a fully descending sorted array.
For beginners, this is a simple and intuitive adjustment. It demonstrates how minor changes in the merging step can reverse the order without modifying the core logic of Bucket Sort.
Frequently Asked Questions (FAQ)
Here are some questions that beginners often have about Bucket Sort in Kotlin.
Q1: What is Bucket Sort?
Bucket Sort is a sorting algorithm that distributes elements into multiple buckets, sorts each bucket individually, and then merges them to form a sorted array.
Q2: When is Bucket Sort most useful?
It works best when the data is evenly distributed over a known range, such as floating-point numbers between 0 and 1.
Q3: Is Bucket Sort stable?
Yes, if the sorting method used inside each bucket is stable, the overall Bucket Sort will also be stable.
Q4: What is the time complexity of Bucket Sort?
The average time complexity is O(n + k), where n is the number of elements and k is the number of buckets.
Q5: Can Bucket Sort handle integers?
Yes, by adjusting the bucket ranges, integers can be sorted efficiently using Bucket Sort.
Conclusion
Bucket Sort is an elegant and efficient sorting algorithm, especially useful for evenly distributed datasets. By dividing the problem into buckets and sorting each bucket individually, it simplifies the sorting process and makes it easy to understand for beginners.
In Kotlin, Bucket Sort can be implemented using lists, arrays, and even custom sorting functions. Whether you work with floating-point numbers, integers, or collections, learning Bucket Sort will strengthen your understanding of sorting algorithms. Try experimenting with different data and bucket sizes, and you’ll see how versatile and practical this algorithm can be in real-world applications.
