選択ソートを図を使って分かりやすく解説(C言語サンプルプログラム付き)

選択ソート解説ページのアイキャッチ

このサイトでは、ここまで「クイックソート」と「マージソート」の解説を行なってきました。

クイックソート解説ページのアイキャッチクイックソートを図を使って分かりやすく解説(C言語サンプルプログラム付き) マージソート解説ページのアイキャッチマージソートを図を使って分かりやすく解説(C言語サンプルプログラム付き)

このページでは、これらと同様のソートアルゴリズムである「選択ソート」について解説します。

選択ソートとは

選択ソートとは前述の通り、ソートアルゴリズムの1つです。

選択ソートには下記のような特徴があります。

  • アルゴリズムが簡単!
  • 使用メモリが少ない(配列一つ分でソートできる)
  • 処理速度が遅い

アルゴリズムが簡単なので、ソートアルゴリズムを最初に学ぶには最適のアルゴリズムです。

処理速度は遅いですが、処理が単純でプログラミングしやすいため、速度がそこまで要求されないような場面では使用される機会も多いと思います。

選択ソートの考え方

選択ソートは与えられたデータの集合に対し、下記の考え方でソートを行うアルゴリズムです。

  • データの集合の中で最小のデータを探索
  • 最小のデータを集合の先頭のデータと交換
  • 先頭のデータを除いたデータの集合をソート
MEMO

上記はデータを昇順に並べる時の考え方になります

降順に並べる際は「最小」を「最大」に、「先頭」を「末尾」に読み替えて考えてください

スポンサーリンク

選択ソートの流れ

続いて選択ソートによってデータがソートされていく流れを解説していきたいと思います。

データの集合の中で最小のデータを探索

選択ソートでは、まずは集合の中で最小のデータを探索します。

集合の中から一番小さいデータを探索

最小のデータがどれであるかは、集合の中の全データを調べないと分からないので、データ数分の比較処理が必要になります。

最小のデータを集合の先頭のデータと交換

続いて、その最小のデータを集合の先頭のデータと交換します。

最小のデータを先頭のデータと交換

この時点で、集合の先頭のデータは最小のデータとなります。つまり、集合の先頭のデータはすでにソート済みであると考えられます。

スポンサーリンク

先頭のデータを除いたデータの集合をソート

集合の先頭のデータはすでにソート済みですので、もうこのデータをソートする必要はありません。

ですので、次はこの先頭のデータを除いた集合のデータのみに対してソートを行います。

先頭を除いたデータの集合をソート

このソートには選択ソートを用います。

つまり、先頭のデータを除いた集合を新たな集合と考え、その新たな集合の中から最小のデータを探索し、そのデータと新たな集合の先頭のデータを交換します。

新たな集合の最小のデータを先頭のデータと交換

これは、元々の集合で考えると、集合の中で2番目に小さいデータと、集合の先頭から2番目のデータを交換することになります。

これにより、元々のデータの集合で考えると、先頭のデータと先頭から2番目のデータがソート済みになります。

ソート済みのデータ

さらに、このソート済みのデータを除いたデータを再び新たな集合と考えて同様の処理を繰り返していきます。

さらに先頭を除いてソート

これにより、集合の先頭側から順々にソートが完了し、ソートを行う対象となる集合のデータ数が減少されていきます。

ソート済みのデータが増え、ソート必要な集合のデータが減っていく様子

最終的に集合のデータ数が1つになるまでこれを繰り返します。

ソートを行うデータ数が1つになった様子

ここまで、集合の中の最小のデータを集合から除外することを繰り返して、集合のデータ数を減らしてきました。したがって、最後に残ったデータは最大のデータとなります。

さらに、他のデータは既にソート済みですので、これにより元々の集合のデータ全てのソートが完了したことになります。つまり、集合のデータが1つになったらソート処理は完了です。

こんな感じで集合のデータが1つになるまで下記を繰り返してソートを行うのが選択ソートです。

  • データの集合の中で最小のデータを探索
  • 最小のデータを集合の先頭のデータと交換
  • 先頭のデータを除いたデータの集合をソート

選択ソートのプログラム

最後に、ここまで解説してきた選択ソートをC言語で実装したサンプルプログラムを紹介しておきます。

ここでは再帰処理を行う場合と行わない場合のサンプルプログラムを紹介します。

再帰処理なしの選択ソートサンプルプログラム

まずは再帰処理を行わない場合の選択ソートを行う関数のサンプルプログラムです。

選択ソート関数(再帰処理なし)
/* 選択ソートを行う関数
 * data[] : ソートを行うデータの集合
 *          (ソート後のデータの集合を格納)
 * left : ソートを行う範囲の開始点
 * right : ソートを行う範囲の終了点
 */
void selectionSort(int data[], int left, int right) {
    int start;
    int i;
    int min;
    int i_min;
    int tmp;

    /* データ数が1の場合はソート済みなのでソート終了 */    
    if (left == right) {
        return;
    }

    /* ソート範囲(開始点)の初期化 */
    start = left;

    /* ソート範囲を狭めながらソート処理 */
    for (start = left; start < right; start++) {

        /* ひとまずソート範囲の先頭を最小値とみなす */
        i_min = start;
        min = data[i_min];

        /* ソート範囲の中から最小値を探索 */
        for (i = start; i <= right; i++) {
            if (min > data[i]) {
                /* 最小値とその値を持つインデックスを更新 */
                min = data[i];
                i_min = i;
            }
        }
        /* ソート範囲の先頭と最小値を交換 */
        tmp = data[start];
        data[start] = data[i_min];
        data[i_min] = tmp;
    }
}

ソートを行う範囲の先頭を start 変数で管理しています。

データの交換が終わったら for 文により start がインクリメントされますので、どんどんソートを行う範囲が狭まっていくことになります。

ソートを行う範囲の制御
/* ソート範囲を狭めながらソート処理 */
for (start = left; start < right; start++) {

ソートを行う範囲の先頭を表す start と末尾を表す right が同じ値になったら、ソートが未完了のデータが1つになったことになりますので処理を終了します。

スポンサーリンク

再帰処理ありの選択ソートサンプルプログラム

次は再帰処理ありの選択ソートを行う関数のサンプルプログラムです(データ数が多すぎるとスタックが溢れてプログラムが異常終了する可能性があるので注意してください)。

選択ソート関数(再帰処理あり)
/* 選択ソートを行う関数
 * data[] : ソートを行うデータの集合
 *          (ソート後のデータの集合を格納)
 * left : ソートを行う範囲の開始点
 * right : ソートを行う範囲の終了点
 */
void selectionSort(int data[], int left, int right) {
    int i;
    int min;
    int i_min;
    int tmp;

    /* データ数が1の場合はソート済みなのでソート終了 */    
    if (left == right) {
        return;
    }

    /* ひとまずソート範囲の先頭を最小値とみなす */
    i_min = left;
    min = data[left];
    

    /* ソート範囲の中から最小値を探索 */
    for (i = left; i <= right; i++) {
        if (min > data[i]) {
            /* 最小値とその値を持つインデックスを更新 */
            min = data[i];
            i_min = i;
        }
    }

    /* ソート範囲の終了点と最小値を交換 */
    tmp = data[left];
    data[left] = data[i_min];
    data[i_min] = tmp;

    /* ソート範囲を狭めて再度選択ソート */
    selectionSort(data, left + 1, right);
}

selectionSort 関数の中で selectionSort 関数を呼び出しています。

この時にソート範囲の先頭を表す left+1 して呼び出すことで、どんどんソート範囲を狭めながらソート処理を行なっていくことになります。

ソートを行う範囲の制御
/* ソート範囲を狭めて再度選択ソート */
selectionSort(data, left + 1, right);

また、関数の先頭でデータ数が1つかを判断し、1つであれば即座にソート処理を終了するようにしています。

データが1つの時の処理
/* データ数が1の場合はソート済みなのでソート終了 */    
if (left == right) {
    return;
}

まとめ

このページでは選択ソートについて解説しました。

選択ソートは下記の考え方でデータを並べ替えるソート方法になります。

  • データの集合の中で最小のデータを探索
  • 最小のデータを集合の先頭のデータと交換
  • 先頭のデータを除いたデータの集合をソート

前述の通り、比較的処理内容が分かりやすいですので、アルゴリズム勉強の入門として最適のテーマだと思います。

今回プログラムで示したように、再帰処理なしの場合と再帰処理ありの場合のプログラムを考えることで再帰処理の復習も行えます。

是非一度はプログラミングしてみることをオススメします!

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です