radix sort

基数ソート – 基数ソート。このアルゴリズムは、要素の比較がないという点でカウントソートに似ています。代わりに、要素が *文字ごと* に *バケット* (バケット) にグループ化され、バケットは現在の数値文字のインデックスによって選択されます。時間計算量 – O(nd)。

次のように動作します:

入力は数字 6、12、44、9 になります
リスト (0 ～ 9) のバケットを 10 個作成し、そこに少しずつ数字を追加/並べ替えます。

<オル>

数値内の最大文字数までのカウンター i でループを開始します

インデックス i を右から左に指定すると、各数値に対して 1 つの記号が得られ、記号がない場合は 0 であると見なされます。

記号を数値に変換する

インデックス番号でバケットを選択し、そこに整数を入力します

数値の検索が終了したら、すべてのバケットを数値のリストに変換し直します

ランク順に並べ替えられた数値を取得する

すべての数字がなくなるまで繰り返します

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}")

    }

}

このアルゴリズムには、GPU などで並列実行するためのバージョンもあります。ちょっとした並べ替えオプションもあります。これは非常に興味深く、本当に息をのむようなものに違いありません。