基数ソートとバケットソートとは？

基数ソートとバケットソートとは、値どうしを比較せずに整列する方式。バケットソートは値の範囲を区切った入れ物に振り分けて並べ、基数ソートは下位の桁から順に「桁の値ごとに振り分けて集める」ことを繰り返す。比較を行わないため、条件次第では要素数に比例する時間で整列できる。

きすうそーととばけっとそーと

基本情報技術者試験の頻出用語／テクノロジ系

基数ソートとバケットソートの意味

値どうしを比較せずに整列する方式。バケットソートは値の範囲を区切った入れ物に振り分けて並べ、基数ソートは下位の桁から順に「桁の値ごとに振り分けて集める」ことを繰り返す。比較を行わないため、条件次第では要素数に比例する時間で整列できる。

3桁の整数を基数ソートするなら、1の位で0〜9の箱に配り直し、次に10の位、最後に100の位で同じ操作をすると整列が完了する。桁数をkとすると、比較回数ではなく振り分けをk回行うだけで済む。

比較による整列の下限であるO(n log n)より速くできるのは、「値の性質（桁や範囲）を使う」という前提があるため。値の範囲が極端に広いと箱が膨大になり、追加の記憶領域が必要になる欠点も問われる。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。