スポンサードリンク
|
|
情報処理用語集＞ラ＞ラディックスソート（基数整列法） |
|
ｒａｄｉｘ ｓｏｒｔ
ラディックスソートとは、ｒ進数で表現された数値を整理するために行う
整列法である。
基数整列法とも呼ばれる。
下位の桁の数字から２～ｒ－１のｒ個のグループに分類し、
それぞれを併合することを繰り返すことによって行う。
固定桁数の数値の整列に適しており、１０進数で表された数値の場合、
下位の桁から０～９にグループ分けして併合することを繰り返す。
ｋ桁の数値ｎ個のデータの計算量はＯ（ｎｋ）で、安定な整列である。
次のような手順で昇順に整列される。
①整列前のデータ
|
| Ａ（１） |
Ａ（２） |
Ａ（３） |
Ａ（４） |
Ａ（５） |
Ａ（６） |
Ａ（７） |
Ａ（８） |
Ａ（９） |
Ａ（10） |
Ａ（11） |
Ａ（12） |
| ９０ |
２２ |
２４ |
１５ |
３９ |
０２ |
５２ |
４０ |
１３ |
９９ |
５４ |
３１ |
|
②グループ分け：下位から１桁目で、０～９のグループに分ける
|
０のグループ ２のグループ ４のグループ …… ９のグループ
１のグループ ３のグループ ５のグループ
|
③グループの併合：０～９までのグループを順に併合する。
※ここでの併合とは、単に０～９のグループを順に結合することを意味する。
|
| ９０ |
４０ |
３１ |
２２ |
０２ |
５２ |
１３ |
２４ |
５４ |
１５ |
３９ |
９９ |
|
④グループ分け：下位から２桁目で、０～９のグループに分ける
|
０のグループ ２のグループ ４のグループ …… ９のグループ
１のグループ ３のグループ ５のグループ
|
③グループの併合：０～９までのグループを順に併合する。
|
| ０２ |
１３ |
１５ |
２２ |
２４ |
３９ |
４０ |
５２ |
５４ |
３１ |
９０ |
９９ |
|
スポンサードリンク
|
|
Copyright (C) 情報処理用語集 All Rights Reserved
|
|
