Skip to content

Instantly share code, notes, and snippets.

@grandstaish
Created April 6, 2017 05:14
Show Gist options
  • Save grandstaish/dad348b759975d3fb34c2eb2f8497939 to your computer and use it in GitHub Desktop.
Save grandstaish/dad348b759975d3fb34c2eb2f8497939 to your computer and use it in GitHub Desktop.
Basic radix sorting algorithm written in Kotlin
fun IntArray.radixSort(): IntArray {
var result = this
val max = getMax()
var place = 1
while (max / place > 0) {
result = result.countingSort(place)
place *= 10
}
return result
}
fun IntArray.countingSort(place: Int): IntArray {
val result = IntArray(size)
val count = IntArray(10)
for (i in 0 until result.size) {
val digit = (this[i] / place) % 10
count[digit] += 1
}
for (i in 1 until count.size) {
count[i] += count[i - 1]
}
for (i in size - 1 downTo 0) {
val digit = (this[i] / place) % 10
result[count[digit] - 1] = this[i]
count[digit]--
}
return result
}
fun IntArray.getMax(): Int {
var mx = this[0]
for (i in 1..size - 1)
if (this[i] > mx)
mx = this[i]
return mx
}
@grandstaish
Copy link
Author

Usage:

val sortedIntArray = unsortedIntArray.radixSort()

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment