バブルソート(基本交換法)とは

プログラム

バブルソート(基本交換法)とは | 分かりやすく図解で解説

はじめに

情報処理試験問題でよく登場する整列アルゴリズムの問題。

基本的な整列アルゴリズムには「バブルソート」「選択ソート」「挿入ソート」があります。そしてより高速な整列アルゴリズムには「シェルソート」「クイックソート」「ヒープソート」「マージソート」などがあります。

スポンサーリンク

本記事では、隣り合わせの値と比較して整列させていく「バブルソート(基本交換法)」について図解を利用してわかりやすく解説しています。

バブルソート(基本交換法)とは

バブルソートとは、隣り合わせのデータを比較して交換を繰り返していくシンプルな手法です。

  1. 先頭の値と隣合わせの値を比較します。
  2. 左の方が大きければ、入れ替える。小さければそのままとします。
  3. 1と2を繰り返し入れ替えが発生しなくなるまで続けていきます。

 

それでは具体的に図解でバブルソートの流れを説明していきます。

 

暗記ポイント:バブルソートは隣り合わせの値と比較して交換を繰り返していく整列アルゴリズム

1巡目 先頭から隣り合わせと比較していく

まずは先頭の2つを比較

まずは先頭の"4"と隣り合わせの"1"を比較します。

"4"の方が"1"より大きいので、入れ替えます。

バブルソート手順1

続いてさらに隣の"3"と比較

続いてさらに隣にある"3"と比較します。

"4"の方が"3"より大きいので、入れ替えます。

バブルソート手順2

続いてさらに隣の"2"と比較

続いてさらに隣にある"2"と比較します。

"4"の方が"2"より大きいので、入れ替えます。

バブルソート手順3

2巡目 先頭に戻り再び、先頭から隣り合わせと比較していく

先頭に戻り再び先頭の2つを比較

先頭に戻り再び先頭の2つを比較します。先頭の"1"と隣り合わせの"3"を比較します。

"1"の方が小さいので、入れ替えは行わずそのままとします。

バブルソート手順4

スポンサーリンク

続いてさらに隣の"2"と比較

続いてさらに隣にある"2"と比較します。

"3"の方が"2"より大きいので、入れ替えます。

バブルソート手順5

続いてさらに隣の"4"と比較

続いてさらに隣にある"4"と比較します。

"3"の方が小さいので、入れ替えは行わずそのままとします。

バブルソート手順6

3巡目 先頭に戻り入れ替えが行われなくなるまで繰り返す

先頭に戻り再び、先頭から比較を繰り返していきます。

入れ替えが一度も行われなくなればバブルソートは終了です。

バブルソート手順7

 

[基本整列アルゴリズム]

[高速整列アルゴリズム]

\ 参考になりましたか? /

© 2020 ITを分かりやすく解説