目次
はじめに
情報処理試験問題でよく登場する整列アルゴリズムの問題。
基本的な整列アルゴリズムには「バブルソート」「選択ソート」「挿入ソート」があります。そしてより高速な整列アルゴリズムには「シェルソート」「クイックソート」「ヒープソート」「マージソート」があります。
スポンサーリンク
本記事では、隣り合わせの値と比較して整列させていく「バブルソート(基本交換法)」について図解を利用してわかりやすく解説しています。
バブルソート(基本交換法)とは
バブルソートとは、隣り合わせのデータを比較して交換を繰り返していくシンプルな手法です。
- 先頭の値と隣合わせの値を比較します。
- 左の方が大きければ、入れ替える。小さければそのままとします。
- 1と2を繰り返し入れ替えが発生しなくなるまで続けていきます。
それでは具体的に図解でバブルソートの流れを説明していきます。
暗記ポイント
バブルソートは隣り合わせの値と比較して交換を繰り返していく整列アルゴリズム
1巡目 先頭から隣り合わせと比較していく
まずは先頭の2つを比較
まずは先頭の"4"と隣り合わせの"1"を比較します。
"4"の方が"1"より大きいので、入れ替えます。
続いて隣の"3"と比較
続いて隣にある"3"と比較します。
"4"の方が"3"より大きいので、入れ替えます。
続いて隣の"2"と比較
続いて隣にある"2"と比較します。
"4"の方が"2"より大きいので、入れ替えます。
2巡目 先頭に戻り再び、先頭から隣り合わせと比較していく
先頭に戻り再び先頭の2つを比較
先頭に戻り再び先頭の2つを比較します。先頭の"1"と隣り合わせの"3"を比較します。
"1"の方が小さいので、入れ替えは行わずそのままとします。
スポンサーリンク
続いて隣の"2"と比較
続いて隣にある"2"と比較します。
"3"の方が"2"より大きいので、入れ替えます。
続いて隣の"4"と比較
続いて隣にある"4"と比較します。
"3"の方が小さいので、入れ替えは行わずそのままとします。
3巡目 先頭に戻り入れ替えが行われなくなるまで繰り返す
先頭に戻り再び、先頭から比較を繰り返していきます。
入れ替えが一度も行われなくなればバブルソートは終了です。
[基本整列アルゴリズム]
[高速整列アルゴリズム]