グレーディングソート

ソートキーとなる値のとり得る範囲を一定間隔の階級に分け、各項目を振り分けて階級テーブルにリンクしていくソート方式。

もちろん1回の振り分けでは完全なソートができないため、同一階級の中でさらに階級を細分するか、他のソート方式を組み合わせて絞り込む必要がある。しかし、本来は精度を犠牲にしてまで高速化したい場合に使われるソート方式であるため振り分けは1回で済ますことが多く、主にポリゴンの描画順序を決める処理などに使われる。

メモリーの書き換えはリンク情報のみで、ソート対象のデータそのものを書き移す必要がないため極めて高速だが、ソート結果からある順位のデータを取り出すためには端からリンクを辿っていかなければならないという欠点がある。

通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)