Radix Sort

Radix Sort – radix sort. The algorithm is similar to counting sort in that there is no comparison of elements, instead elements are *character-by-character* grouped into *buckets* (buckets), the bucket is selected by the index of the current number-character. Time complexity – O(nd).

Works like this:

  • The input will be the numbers 6, 12, 44, 9
  • Let’s create 10 buckets of lists (0-9) into which we will add/sort numbers bit by bit.

Further:

  1. Run a loop with counter i up to the maximum number of characters in the number
  2. At index i from right to left we get one character for each number, if there is no character, then we consider it to be zero
  3. The character is converted to a number
  4. Select a bucket by index – number, put the whole number there
  5. After finishing iterating over numbers, convert all buckets back to a list of numbers
  6. Get numbers sorted by digit
  7. Repeat until all digits run out

Radix Sort example in Scala:

import scala.collection.mutable.ListBuffer
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 the GPU; there is also a variant of bit sort, 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%D0%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

Published by demensdeum