radix sort

Classificação de raiz – classificação de raiz. O algoritmo é semelhante à classificação por contagem, pois não há comparação de elementos; em vez disso, os elementos são agrupados *caractere por caractere* em *baldes* (baldes), o balde é selecionado pelo índice do caractere numérico atual. Complexidade de tempo – O(nd).

Funciona mais ou menos assim:

A entrada serão os números 6, 12, 44, 9
Criaremos 10 grupos de listas (0-9), nos quais adicionaremos/classificaremos números pouco a pouco.

Inicie um loop com o contador i até o número máximo de caracteres no número
Pelo índice i da direita para a esquerda obtemos um símbolo para cada número; se não houver símbolo, então assumimos que é zero

;

Converta o símbolo em um número
Selecione um intervalo por número de índice e coloque o número inteiro lá
Depois de terminar de pesquisar os números, converta todos os grupos novamente em uma lista de números
Obter números classificados por classificação
Repita até que todos os dígitos desapareçam

Exemplo de classificação Radix em 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}")

    }

}

O algoritmo também possui uma versão para execução paralela, por exemplo em uma GPU; Há também uma opção de classificação, que deve sermuito interessante e realmente de tirar o fôlego!