前回、探索アルゴリズム(線形探索・二分探索)を整理しました。今回は、探索と並んでよく出題される「ソートアルゴリズム」の基本、バブルソートと選択ソートを整理します。
ソートアルゴリズムとは
ソートアルゴリズムとは、配列の中の値を、昇順(小さい順)や降順(大きい順)に並べ替えるための手順のことです。前回学んだ二分探索も、あらかじめ整列された配列が前提でした。このソートの仕組みを理解しておくことが、探索の理解にもつながります。
バブルソートとは
バブルソートは、隣り合う要素どうしを比較し、順番が逆であれば入れ替える、という操作を繰り返す方法です。
例えば「５、２、４、１」という配列を昇順に並べ替える場合、まず５と２を比較して入れ替え、次に５と４を比較して入れ替え、次に５と１を比較して入れ替える、というように、隣どうしの比較と入れ替えを、配列の端まで繰り返します。この１周が終わると、いちばん大きい値が端に移動している状態になります。
これを、整列が完了するまで何周も繰り返すのが、バブルソートの基本的な考え方です。値が少しずつ端に移動していく様子が、水の泡(バブル)が浮かび上がる様子に似ていることから、この名前がついています。
選択ソートとは
選択ソートは、配列の中から最小値(または最大値)を探し出し、それを先頭の未整列の位置と入れ替える、という操作を繰り返す方法です。
例えば「５、２、４、１」という配列であれば、まず配列全体から最小値の１を探し出し、先頭の５と入れ替えます。次に、先頭を除いた残りの部分から最小値を探し、その位置と入れ替える、という操作を繰り返していきます。
バブルソートが「隣どうしを比較して入れ替える」のに対して、選択ソートは「全体から最小値を探してから入れ替える」という違いがあります。
トレースするときの注意点
ソートのトレース問題では、「何回目の比較・入れ替えが終わった時点で、配列がどうなっているか」を問われることがよくあります。
自分は、配列の状態を、比較や入れ替えのたびに、そのまま書き出していく練習をしています。頭の中だけで最終形をイメージしようとすると、途中の状態を問われたときに答えられなくなるため、面倒でも１ステップずつ書き出すようにしています。
２つのソートの違いを整理する
- バブルソート:隣どうしを比較し、順番が逆なら入れ替える。これを繰り返す
- 選択ソート:全体から最小値(または最大値)を探し、決まった位置と入れ替える。これを繰り返す
どちらも「未整列の範囲を、少しずつ狭めていく」という共通点がありますが、「隣どうしを見るか」「全体を見渡すか」という視点の違いを意識すると、混同しにくくなりました。
学習してみた感想
ソートアルゴリズムは、名前だけを聞くと難しそうですが、実際に手を動かして数字を並べ替えてみると、動作自体は素直な仕組みでした。ただ、比較・入れ替えの回数が増えると、どこまで進んだか分からなくなりやすいので、書き出しながら追う練習を続けていきたいと思います。
次回は、③に戻り、学習３週目の振り返りとして、アルゴリズムに苦戦した話をまとめます。
