Radix Sort is a radix sort. The algorithm is similar to counting sort in that there is no comparison of elements, instead, elements are grouped *symbolically* into *buckets*, the bucket is selected by the index of the current number-symbol. Time complexity is O(nd).
It works something like this:
- As input we receive the numbers 6, 12, 44, 9
- Let’s create 10 list buckets (0-9) into which we will add/sort numbers bitwise.
Next:
- Start a loop with counter i until the maximum number of characters in the number
- According to the index i from right to left we get one symbol for each number, if there is no symbol, we consider it zero
- Convert the symbol to a number
- We select a bucket by index – number, put the number there in full
- After we finish iterating over the numbers, we transform all the buckets back into a list of numbers
- We get numbers sorted by rank
- Repeat until all the digits are gone
Radix Sort example in Scala:
import scala.util.Random.nextInt
object RadixSort {
def main(args: Array[String]) = {
var maxNumber = 200
var numbersCount = 30
var maxLength = maxNumber.toString.length() - 1
var referenceNumbers = LazyList.continually(nextInt(maxNumber + 1)).take(numbersCount).toList
var numbers = referenceNumbers
var buckets = List.fill(10)(ListBuffer[Int]())
for( i <- 0 to maxLength) { numbers.foreach( number => {
var numberString = number.toString
if (numberString.length() > i) {
var index = numberString.length() - i - 1
var character = numberString.charAt(index).toString
var characterInteger = character.toInt
buckets.apply(characterInteger) += number
}
else {
buckets.apply(0) += number
}
}
)
numbers = buckets.flatten
buckets.foreach(x => x.clear())
}
println(referenceNumbers)
println(numbers)
println(s"Validation result: ${numbers == referenceNumbers.sorted}")
}
}
The algorithm also has a version for parallel execution, for example on a GPU; there is also a bit sorting variant, which is probably very interesting and truly breathtaking!
Links
https://gitlab .com/demensdeum/algorithms/-/blob/master/sortAlgorithms/radixSort/radixSort.scala
Sources
https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%80%D0%B0%D0%B7%D1%80%D1%8F%D 0%B4%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0% BA%D0%B0
https://www.geeksforgeeks.org/radix-sort/
https://www.youtube.com/watch?v=toAlAJKojos
https://github.com/gyatskov/radix-sort
