C言語のきほん｜アルゴリズムとソート

C言語のきほん｜アルゴリズムとソート

同じ答えでも“手順”で速さが変わる！アルゴリズムとソートで、考え方の筋トレをしよう。

アルゴリズムって聞くと難しそうに感じるかもしれないけど、実はとてもシンプルで、ひとことで言うと 問題を解くための手順書 です。
コンピュータは賢そうに見えても、こちらが「何を、どの順番で、どうやってやるか」をはっきり指示しないと動けません。

たとえば「2つの数を足して表示する」みたいな簡単なことでも、

1. 1つ目を入力する
2. 2つ目を入力する
3. 足す
4. 表示する

という手順が必要になります。これをきちんと並べて実行できる形にしたものがアルゴリズムで、そのアルゴリズムをC言語で書き下すのがプログラミングです。

そして、アルゴリズムの入り口としてとても学びやすい題材が ソート（並べ替え）。
同じ「小さい順に並べる」でも、やり方（手順）によって動きが変わって、考え方の違いが見えやすいんです。

アルゴリズムって何？

アルゴリズムは「やるべきことを指示する手順書」です。
大事なのは、手順が 曖昧じゃない こと。

たとえば人間なら「いい感じに並べて」と言われても何となくできますが、コンピュータには無理です。
だから、

• どこから始める？
• 何と何を比べる？
• 交換する条件は？
• 何回繰り返す？

みたいなことを、全部はっきり書きます。

アルゴリズムをプログラムにするとは

頭の中の手順を、C言語の for や if を使って「実行できる形」に落とし込むことです。
この作業に慣れると、難しい問題でも「手順に分解して整理する」クセが身についてきます。

ソートはアルゴリズムの練習にぴったり

「数字を小さい順に並べる」だけでも、いろんな手順が考えられます。

• 隣同士を比べて入れ替え続ける
• いちばん小さいものを探して先頭に持ってくる
• 途中に差し込むように並べる
• うまく分割して高速に並べる

この章では基本として、次の2つを扱います。

• バブルソート（基本交換法）：隣り合う要素を交換して、大きいものを後ろへ追いやる
• セレクションソート（基本選択法）：最小の要素を選んで前に置く

バブルソート（基本交換法）の考え方

手順のイメージ

バブルソートは、隣り合う2つを見比べて、順番が逆なら交換します。これを端まで繰り返すと、最大値が最後に“押し出される”感じになります。

左から順に比較 → 逆なら交換 → 端まで行ったら
いちばん大きい値が最後尾に移動
次は最後尾の手前までで繰り返す

具体例（配列を別の値に置き換え）

例として、次の並びを小さい順にします。

[6, 1, 4, 9, 2]

1回目の端までの比較で、最大値 9 が最後に行くのがポイントです。

• 6 と 1 → 交換 → [1, 6, 4, 9, 2]
• 6 と 4 → 交換 → [1, 4, 6, 9, 2]
• 6 と 9 → 交換なし → [1, 4, 6, 9, 2]
• 9 と 2 → 交換 → [1, 4, 6, 2, 9]

この時点で 9 は確定で最後尾です。次は最後尾を除いた範囲で続けます。

バブルソートのシンプル実装例

ファイル名：7_1_1.c

#include <stdio.h>

int main(void)
{
    int a[] = {6, 1, 4, 9, 2};
    int n = 5;
    int i, j, temp;

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

    /* バブルソート：隣同士を比べて交換していく */
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }

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

    printf("メッセージ: 大きい値が右へ押し出されるのがバブルソートだよ。\n");
    return 0;
}

セレクションソート（基本選択法）の考え方

手順のイメージ

セレクションソートは、「残っている範囲から最小を探して、先頭に持ってくる」を繰り返します。

1回目：全体から最小を探す → 先頭と交換
2回目：2番目以降から最小を探す → 2番目と交換
...

具体例（配列を別の値に置き換え）

1回目：最小は 1 → 先頭の 6 と交換 → [1, 4, 6, 9, 2]
2回目：残り [4, 6, 9, 2] の最小は 2 → 4 と交換 → [1, 2, 6, 9, 4]
…という感じで、前から順に確定していきます。

セレクションソートのシンプル実装例

ファイル名：7_1_2.c

#include <stdio.h>

int main(void)
{
    int a[] = {6, 4, 1, 9, 2};
    int n = 5;
    int i, j, min, temp;

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

    /* セレクションソート：最小を探して前に置く */
    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }

        /* 最小の位置が変わっていたら交換 */
        if (min != i) {
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }

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

    printf("メッセージ: 最小を選んで前から確定するのがセレクションソートだよ。\n");
    return 0;
}

バブルとセレクションの違いを整理

どっちも学習用として最高で、「手順を言語化してからコードに落とす」練習になります。

もう少し先の話（ソートは他にもある）

ソートには他にも、

• インサーションソート（基本挿入法）
• クイックソート
• マージソート

などがあり、速さや特徴が変わります。
ただ、いきなり難しいものに行くより、まずはバブルとセレクションで「手順を実装する感覚」を掴むのが一番の近道です。