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