BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
バブルソート
隣同士を比べて交換する
バブルソートは、隣り合う要素を比較し、順序が逆なら交換する操作を繰り返して整列する方法です。一回の走査で大きな値が末尾へ移るなど、要素が少しずつ目的の位置へ動きます。処理が単純で追いやすい一方、大量のデータでは比較や交換が多くなりやすい方法です。
Pythonによる例
def bubble_sort(values):
result = list(values)
for end in range(len(result) - 1, 0, -1):
changed = False
for index in range(end):
if result[index] > result[index + 1]:
result[index], result[index + 1] = (
result[index + 1], result[index]
)
changed = True
if not changed:
break
return result
左から右へ走査し、右端の確定済みの範囲を広げる例です。
一回の走査の意味
4、1、3、2を左から比べると、4が順に右へ動き、最初の走査後は1、3、2、4になります。この時点で最大値の位置は決まっていますが、残りはまだ整列していません。次は確定した4を除く範囲を調べます。問題で走査方向が逆なら、どちらの端が先に確定するかも変わります。
計算量と早期終了
標準的な最悪時の比較回数はO(n²)です。交換が一度もなかった走査で終了する工夫を入れると、既に整列したデータでは少ない処理で終われます。ただし、その工夫がない実装に同じ最良時の説明を当てはめてはいけません。計算量はアルゴリズム名だけでなく、提示された手順に基づいて考えます。
安定性と試験の要点
等しい値を交換しない方式なら、同じキーを持つ要素の相対順序を保てます。これは安定な整列という性質です。試験では一回の比較、一回の走査、全体の完了を区別し、比較のたびに配列を書き換えます。最小値を探して一度交換する選択ソートと、隣同士を逐次交換するバブルソートの違いを押さえましょう。
参考資料
内容確認日:2026-11-13
この用語に関連する問題
1問用語一覧
10件パーミッション・マーケティング
パーミッション・マーケティング とは、パーミッション(permition)は、日本語で 許可。 この事から、お客様より許可をとった上で行うマーケティング手法にな...
バイラルマーケティング
バイラル・マーケティングとは、 英語表記では Viral marketing . バイラルとは、「ウィルス性の」という意味であり、口コミなどでウィルスのように繁殖して広...
バックアップ
復元のために別の状態を保存する バックアップは、障害や誤操作などで失われたデータを戻せるよう、別の保存先や世代にデータを保管することです。現在のデータ...
ハッシュ表
キーから格納場所を求める ハッシュ表は、キーにハッシュ関数を適用して格納場所の候補を求め、対応する値を保存・検索するデータ構造です。社員番号から社員情...
ハッシュ関数
意味と用途 ハッシュ関数は、入力データから一定の規則で値を計算する関数です。暗号の分野では、任意の長さのデータから固定長のハッシュ値を得る仕組みがよく...
バッファオーバーフロー
確保した領域を越えて書き込む バッファオーバーフローは、データを一時的に置くためのメモリー領域に、その容量を超えて書き込んでしまう問題です。隣接するデ...
バブルソート
隣同士を比べて交換する バブルソートは、隣り合う要素を比較し、順序が逆なら交換する操作を繰り返して整列する方法です。一回の走査で大きな値が末尾へ移るな...
バリュー・チェーン
バリューチェーン分析とは、企業の価値の連鎖と呼ばれるもので、企業が生み出す付加価値の繋がりを分類したものである。 5つの主活動と4つの支援活動からなる。...
パレート図
値が降順にプロットされた棒グラフとその累積構成比を表す折れ線グラフを組み合わせた複合グラフ。 どの問題がどの程度占めているか、また、いくつ改善すれば全...
幅優先探索
近いところから順に調べる 幅優先探索は、開始点の隣接頂点を調べ、次にその一段先を調べるように、距離の層を広げていく探索方法です。BFSと略します。先に見つ...