C言語の基本｜アルゴリズムとソート

C言語の基本｜アルゴリズムとソート

同じ結果でも手順が変われば動きも変わる。アルゴリズムとソートで、問題を順序立てて解く力を身につけよう。

アルゴリズムという言葉を聞くと、少し難しそうに感じるかもしれません。しかし、基本的な意味はとてもシンプルです。

アルゴリズムとは、問題を解決するための手順です。

コンピュータは、人間のように状況を見て判断したり、曖昧な指示から意図を読み取ったりすることができません。そのため、何を、どの順番で、どのような条件で実行するのかを、はっきり指示する必要があります。

たとえば、2つの整数を足して結果を表示するだけでも、次のような手順が必要です。

1. 1つ目の整数を受け取る
2. 2つ目の整数を受け取る
3. 2つの整数を加算する
4. 加算結果を表示する

このように、処理を順番に整理したものがアルゴリズムです。そして、そのアルゴリズムをC言語の文法を使って、コンピュータが実行できる形にする作業がプログラミングです。

アルゴリズムを学ぶ題材として分かりやすいものに、ソートがあります。ソートとは、複数のデータを決められた順番に並べ替える処理です。

同じ小さい順への並べ替えでも、比較する場所や交換するタイミングによって、処理の進み方が変わります。この記事では、基本的なバブルソートとセレクションソートを使って、アルゴリズムをC言語で表現する流れを見ていきます。

アルゴリズムとは

アルゴリズムは、目的を達成するために必要な処理を、実行できる順番に並べた手順書です。

大切なのは、処理の内容が曖昧になっていないことです。

人間なら、数字を小さい順にうまく並べてくださいと指示されても、意味を考えながら作業できます。しかし、コンピュータに同じ指示を与えても、具体的な手順がなければ処理できません。

並べ替えを実行させるには、少なくとも次の内容を明確にする必要があります。

• どの要素から比較を始めるのか
• どの要素とどの要素を比較するのか
• どのような条件で交換するのか
• 交換するときに値をどのように移動するのか
• 比較をどこまで繰り返すのか
• どの時点で並べ替えを終了するのか

これらの手順がはっきりしていれば、コンピュータはその順番に従って処理できます。

図1：アルゴリズムをC言語の処理に変換する流れ

この図から分かること

プログラムを作るときは、いきなりC言語のコードを書き始めるのではなく、最初に目的と処理手順を整理します。

たとえばソートでは、比較、交換、繰り返しという小さな処理に分解します。そのうえで、繰り返しをfor、交換条件の判定をifで記述すれば、アルゴリズムを実行可能なプログラムにできます。

複雑に見える問題でも、小さな処理に分けて順番を決めることで、コードに置き換えやすくなります。

アルゴリズムをプログラムにする流れ

頭の中で考えた手順を、コンピュータが実行できる形に置き換えるには、C言語の制御構文や変数を使います。

ソートでは、配列の要素をforで順番に調べます。要素の大小関係をifで判定し、順番が正しくない場合は一時変数を使って交換します。

このように、アルゴリズム上の手順とC言語の処理を対応させることが、プログラムを組み立てる基本になります。

ソートがアルゴリズムの学習に適している理由

ソートは、複数のデータを一定の規則に従って並べ替える処理です。

数値を小さい順に並べることを昇順、大きい順に並べることを降順といいます。この記事では、数値を小さい順に並べる昇順を扱います。

同じ昇順でも、さまざまな並べ替え方があります。

• 隣り合う要素を比較して交換する
• 残っている要素から最小値を探す
• 整列済みの範囲へ適切な位置に挿入する
• データを複数の範囲に分割して並べ替える

どの方法でも、最終的には同じ並びになることがあります。しかし、比較する場所、交換する回数、確定する要素の位置などは異なります。

処理の途中経過を目で追いやすいため、ソートはアルゴリズムの違いを学ぶ題材に向いています。

ここでは、次の2つを取り上げます。

バブルソートとセレクションソートは、どちらも比較と交換を繰り返します。ただし、比較する要素と確定していく方向が異なります。

バブルソートの考え方

バブルソートは、隣り合う2つの要素を比較し、左側の値が右側の値より大きければ交換する方法です。

左から右へ比較を進めると、大きい値が少しずつ右側へ移動します。端まで比較すると、その範囲で最も大きい値が右端に確定します。

基本的な手順は次のとおりです。

1. 配列の先頭から隣り合う2つの要素を比較する
2. 左側の値が大きければ2つの値を交換する
3. 比較位置を1つ右へ移動する
4. 比較範囲の右端まで同じ処理を繰り返す
5. 確定した右端を比較範囲から除外する
6. 残りの範囲で比較と交換を繰り返す

外側の繰り返しが1回終わるたびに、右側の要素が1つずつ確定します。そのため、次の繰り返しでは、すでに確定した要素を比較する必要がありません。

バブルソートの動きを具体例で確認する

次の配列を小さい順に並べます。

[8, 3, 7, 1, 5]

最初の端までの比較では、隣り合う要素を左から順番に調べます。

1. 8と3を比較する
   8のほうが大きいため交換します。
   [3, 8, 7, 1, 5]
2. 8と7を比較する
   8のほうが大きいため交換します。
   [3, 7, 8, 1, 5]
3. 8と1を比較する
   8のほうが大きいため交換します。
   [3, 7, 1, 8, 5]
4. 8と5を比較する
   8のほうが大きいため交換します。
   [3, 7, 1, 5, 8]

これで、配列内の最大値である8が右端に移動しました。8の位置は確定したため、次の比較では右端を除外します。

2回目の端までの比較が終わると、次に大きい7が右から2番目に確定します。この処理を繰り返すことで、配列全体が小さい順に並びます。

図2：バブルソートで最大値が右端へ移動する流れ

この図から分かること

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

最初は8と3を比較し、順番が逆なので交換します。その後も8と右隣の値を比較しながら交換するため、8が少しずつ右へ移動します。

1回の端までの比較が終わると、その範囲で最も大きい値が右端に確定します。次の繰り返しでは確定した右端を除外できるため、比較する範囲が少しずつ短くなります。

隣り合う値を比較して昇順に並べるプログラム

#include <stdio.h>

int main(void)
{
    int values[] = {8, 3, 7, 1, 5};
    int size = 5;
    int i, j, temp;

    printf("並べ替え前: ");
    for (i = 0; i < size; i++) {
        printf("%d ", values[i]);
    }
    printf("\n");

    /* バブルソートで大きい値を右側へ移動する */
    for (i = 0; i < size - 1; i++) {
        for (j = 0; j < size - 1 - i; j++) {
            if (values[j] > values[j + 1]) {
                temp = values[j];
                values[j] = values[j + 1];
                values[j + 1] = temp;
            }
        }
    }

    printf("並べ替え後: ");
    for (i = 0; i < size; i++) {
        printf("%d ", values[i]);
    }
    printf("\n");

    printf("バブルソートで大きい値を右側へ移動しました。\n");

    return 0;
}

ファイル名：7_1_1.c

実行結果の例

並べ替え前: 8 3 7 1 5
並べ替え後: 1 3 5 7 8
バブルソートで大きい値を右側へ移動しました。

バブルソートのプログラムを詳しく確認する

valuesは、並べ替える5つの整数を格納する配列です。

最初のforでは、配列の要素を先頭から順番に表示しています。これにより、並べ替える前の状態を確認できます。

ソート処理では、forを二重に使っています。

外側のforは、端までの比較を繰り返すための処理です。要素数が5個の場合、最大で4回繰り返せばすべての位置を確定できます。そのため、iがsize - 1より小さい間だけ処理します。

内側のforは、隣り合う要素を比較するための処理です。values[j]が左側の要素、values[j + 1]が右側の要素を表します。

外側のforが1回終わるたびに、右端から1つずつ要素が確定します。そのため、内側のforの条件をsize - 1 - iとし、確定済みの要素を比較対象から除外しています。

ifでは、左側のvalues[j]が右側のvalues[j + 1]より大きいかを判定します。条件が成立した場合は、次の3段階で値を交換します。

1. 左側の値をtempへ一時保存する
2. 右側の値を左側へ代入する
3. tempに保存していた値を右側へ代入する

一時変数tempを使わずに一方の値を上書きすると、交換前の値が失われてしまいます。2つの値を安全に入れ替えるためには、一方を一時的に保存する必要があります。

セレクションソートの考え方

セレクションソートは、まだ並び順が確定していない範囲から最小値を探し、その範囲の先頭と交換する方法です。

最小値を選択して前へ移動するため、基本選択法とも呼ばれます。

基本的な手順は次のとおりです。

1. 未整列範囲の先頭を最小値の候補にする
2. 候補と後ろの要素を順番に比較する
3. より小さい値が見つかったら、その位置を記録する
4. 未整列範囲の最後まで最小値を探す
5. 見つけた最小値を未整列範囲の先頭と交換する
6. 確定した先頭を除外して同じ処理を繰り返す

バブルソートでは右側から大きい値が確定しますが、セレクションソートでは左側から小さい値が確定します。

セレクションソートの動きを具体例で確認する

次の配列を小さい順に並べます。

[8, 5, 2, 7, 3]

最初は配列全体が未整列の範囲です。

• 1回目は、8を最小値の候補として、5、2、7、3と順番に比較します。最小値は2なので、先頭の8と交換します。
  [2, 5, 8, 7, 3]
  これで、先頭の2が確定しました。
• 2回目は、先頭の2を除いた範囲から最小値を探します。
  [5, 8, 7, 3]
  この範囲の最小値は3です。3を範囲の先頭にある5と交換します。
  [2, 3, 8, 7, 5]
• 3回目は、8、7、5の中から最小値を探します。
  [ 8, 7, 5]
  この範囲の最小値は5です。最小値の5を8と交換します。
  [2, 3, 5, 7, 8]

このように、未整列範囲の最小値を探して先頭へ移動することで、左側から順番に位置が確定します。

未整列範囲の最小値を選んで昇順に並べるプログラム

ファイル名：7_1_2.c

#include <stdio.h>

int main(void)
{
    int values[] = {8, 5, 2, 7, 3};
    int size = 5;
    int i, j, min_index, temp;

    printf("並べ替え前: ");
    for (i = 0; i < size; i++) {
        printf("%d ", values[i]);
    }
    printf("\n");

    /* セレクションソートで最小値を左側へ移動する */
    for (i = 0; i < size - 1; i++) {
        min_index = i;

        for (j = i + 1; j < size; j++) {
            if (values[j] < values[min_index]) {
                min_index = j;
            }
        }

        /* 最小値が別の位置にある場合は交換する */
        if (min_index != i) {
            temp = values[i];
            values[i] = values[min_index];
            values[min_index] = temp;
        }
    }

    printf("並べ替え後: ");
    for (i = 0; i < size; i++) {
        printf("%d ", values[i]);
    }
    printf("\n");

    printf("セレクションソートで最小値を左側へ移動しました。\n");

    return 0;
}

実行結果の例

並べ替え前: 8 5 2 7 3
並べ替え後: 2 3 5 7 8
セレクションソートで最小値を左側へ移動しました。

セレクションソートのプログラムを詳しく確認する

valuesには、並べ替えの対象となる5つの整数が保存されています。sizeには配列の要素数である5を保存しています。

外側のforで使用するiは、今回最小値を配置する位置を表しています。iが0なら配列の先頭、iが1なら左から2番目の位置を確定します。

各繰り返しの最初に、min_indexへiを代入します。これにより、未整列範囲の先頭を最小値の候補にします。

内側のforは、i + 1の位置から配列の最後まで調べます。現在のvalues[j]が最小値候補のvalues[min_index]より小さい場合は、min_indexをjへ変更します。

内側のforが終了した時点で、min_indexには未整列範囲内の最小値の位置が保存されています。

min_indexとiが異なる場合は、最小値が未整列範囲の先頭以外にあることを意味します。その場合はtempを使ってvalues[i]とvalues[min_index]を交換します。

最小値が最初から未整列範囲の先頭にあった場合は、min_indexとiが同じになります。この場合は交換する必要がないため、交換処理を実行しません。

バブルソートとセレクションソートの違い

バブルソートは、隣り合う要素の順番が逆になるたびに交換します。そのため、1回の端までの比較で複数回交換することがあります。

セレクションソートは、未整列範囲を最後まで調べてから最小値を先頭と交換します。そのため、バブルソートより交換回数が少なくなりやすいという違いがあります。

どちらもforを二重に使って比較を繰り返しますが、値を確定する方法と方向が異なります。

図3：バブルソートとセレクションソートの違い

この図から分かること

バブルソートは、隣り合う値を比較しながら大きい値を右へ移動させます。端まで比較すると、最大値が右側に確定します。

セレクションソートは、未整列範囲全体から最小値を探します。最小値を範囲の先頭と交換するため、小さい値が左側から確定します。

どちらも最終的には同じ昇順の配列を作れますが、比較する方法、交換するタイミング、確定していく方向が異なります。

ほかのソートアルゴリズム

ソートには、バブルソートとセレクションソート以外にもさまざまな方法があります。

インサーションソートは、手元のカードを順番に並べるような考え方です。左側の整列済み範囲を広げながら、新しい値を適切な位置に挿入します。

クイックソートは、基準となる値より小さいグループと大きいグループに分けて並べ替えます。

マージソートは、データを小さな単位に分割し、順番を整えながら結合します。

それぞれ比較方法やデータの移動方法が異なるため、処理の特徴も変わります。まずはバブルソートとセレクションソートを通して、比較、条件分岐、交換、繰り返しという基本的な手順をC言語で表現できるようになることが大切です。