ソートアルゴリズムを初心者向けに徹底解説【基本情報技術者試験対策】

基本情報技術者試験の対策としてバブルソート、挿入ソート、選択ソート、クイックソートを図で分かりやすく説明します。

本記事は配列を理解している必要があります。配列の説明は「データ構造のリストと配列」を参照ください。

ソートとは

ソートとは、データを決められた順番に並べ替える処理のことです。

例えば、ネットショップで商品を「価格が安い順」に表示したり、テストの点数を「高い順」に並べたりする処理もソートの一例です。

ソートアルゴリズムにはさまざまな種類がありますが、多くのアルゴリズムはデータ同士を比較し、必要に応じて位置を入れ替えることで並べ替えを行います。

例えば、隣り合うデータを比較して交換する方法や、最も小さいデータを探して先頭へ移動する方法などがあります。

昇順（しょうじゅん）：小さいものから大きいものへ並べること

降順（こうじゅん）：大きいものから小さいものへ並べること

ソートにはいくつかのアルゴリズムがあります。

基本情報技術者試験では次のソートが出題されます。

バブルソートは、隣り合うデータを比較し、順番が逆であれば交換することを繰り返して並べ替えるソートアルゴリズムです。

データを交換するたびに、大きい値（昇順の場合）が少しずつ右側へ移動していく様子が、水中の泡（バブル）が上へ浮かんでいくように見えることから「バブルソート」と呼ばれています。

バブルソートでは、隣り合う2つのデータを比較します。

昇順（小さい順）に並べる場合は、左側のデータが右側より大きければ位置を交換します。

この処理を配列の最後まで繰り返すことで、下の例のように最も大きい値が最後尾へ移動します。

その後、再び先頭から比較を行い、並べ替えが完了するまで同じ処理を繰り返します。

全体的な流れとしては下のようになります。

上の例では左から順に比較しましたが、右から順に比較してもソートは可能です。
右から順に比較した場合は、左側からソート済みとなります。

選択ソートは、配列において未整列の範囲から最小値（または最大値）を探し、先頭のデータと交換することを繰り返して並べ替えるソートアルゴリズムです。

バブルソートのように隣同士を何度も交換するのではなく、1回のループで最小値を1つ見つけて交換するという点が特徴です。

選択ソートの基本的な流れは、次のとおりです。

挿入ソートでは、左側のデータを「すでに並んでいる」と考えながら処理を進めます。

新しいデータを1つ取り出し、並んでいる部分を後ろから比較して、正しい位置へ挿入します。

挿入ソートの流れは、次のとおりです。

4つの要素の配列を例に挿入ソートの流れを見てみます。

まずは未ソートの左端「1」を取り出して比較をしていきます。

続いて「4」です。

続いて「2」です。

クイックソートは、基準となる値（ピボット）を決め、その値より小さいデータと大きいデータに分けながら並べ替えるソートアルゴリズムです。

クイックソートの流れは、次のとおりです。

基準となる値「ピボット」を決める
配列の先頭からピボット以上の要素を探索し、見つかった位置を得る
配列の末尾からピボット以下の要素を探索し、見つかった位置を得る
上の②と③で見つけた位置どうしの値を交換する。
ただし、②と③の位置が衝突している場合は交換せず、配列の先頭～②の位置-1・③の位置+1～末尾の位置のグループでクイックソートを実行する（再起処理）

5つの要素の配列を例に挿入ソートの流れを見てみます。