第２章４９ソートの仕組み（バブルソート）

#C11仕様 #C言語 #ゲームプログラミング

イチからゲーム作りで覚えるC言語

連載ページ一覧へ

第２章４８共用体(union)を使う : PREV

NEXT : 第２章５０列挙型（enum）を扱う :

概要

プログラムの中で数値の順番に配列を並べる、というような処理を行いたいことは良くあるかと思います。

このような数値の大小や、特定の条件でデータを並べなおす処理をソートと呼びます。

例えば、ランキングでスコアの高い順に並べなおしたり、検索結果を名前のアルファベット順に並べなおしたりなど、用途は非常に多いです。

昇順と降順

数字やアルファベットをソートするとき、昇順と降順について知っておくとよいです。

昇順（しょうじゅん）は「小さい順や条件にしたがって順番に並べる」事で、降順は「大きい順、条件にしたがって逆に並べる」事です。

たとえば、「5,2,4,88,30」という数字の並びを昇順にしてみると、「2 → 4 → 5 → 30 → 88」となります。また、降順にしてみると「88 → 30 → 5 → 4 → 2」という順番になります。

スコアのソート

今回は、得点（score）を昇順でソートしてみます。ソートには非常にシンプルな「バブルソート（Bubble Sort）」というアルゴリズムを使って実装してみます。

bubblesort.c

#include <stdio.h>
#define LENGTH 5
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
int main() {
    int score[LENGTH] = { 5, 2, 4, 88, 30 };

    // score 配列を Bubble Sort する
    for (int i = 0; i < LENGTH - 1; i++) {
        for (int j = 0; j < LENGTH - i - 1; j++) {
            if (score[j] > score[j + 1]) {
                swap(&score[j], &score[j + 1]);
            }
        }
    }
    // ソートした結果を表示
    for (int c = 0; c < 5; c++) {
        printf("%d, ", score[c]);
    }
}

実行すると下のような結果になります。

実行結果

2, 4, 5, 30, 88,

ちゃんと想定したとおりの昇順でスコアがソートされていますね！

では、バブルソートがどのようにして動作しているかを確認していきます。

コードの確認

main 関数から確認していきます。 9 行目で、今回ソートしたい対象の配列のデータが宣言＆初期化されています。 LENGTH は事前に定数の 5 と define ディレクティブで宣言されているため、コンパイルする時には、全て 5 に置き換わっています。

bubblesort.c

int main() {
    int score[LENGTH] = { 35, 8, 2, 18, 3 };

    // score 配列を Bubble Sort する
    for (int i = 0; i < LENGTH - 1; i++) {
        for (int j = 0; j < LENGTH - 1; j++) {
            if (score[j] > score[j + 1]) {
                swap(&score[j], &score[j + 1]);
            }
        }
    }

11 行目からが Bubble Sort のプログラムです。

二つの for 文でループで囲んでいて、ちょっと見づらいですね。内側の for 文の中身から動きを確認していきましょう。

        for (int j = 0; j < LENGTH - 1; j++) {
            if (score[j] > score[j + 1]) {
                swap(&score[j], &score[j + 1]);
            }
        }

隣り合う要素同士（ score[j] と score[j+1] を比較して、左側の要素の方が右側の要素よりも大きい時、二つの要素の中身を交換（swap）しています。これを配列の最初から最後まで繰り返します。

3582183

一度この内側の for 文を実行すると配列は下のような結果になります。

8218335

一番大きな数が、一番右側まで移動していますね。

もう一度この内側の for 文が実行されると下のような結果になります。

2831835

2 番目に大きな数字が、ちゃんと右から二番目に移動しています。

このように n 回実行すると、n 番目に大きな数字が、ちゃんと昇順でソートされていきます。このように、大きな数字が実行するたびに右側に寄っていく姿が、泡がポコポコ上っていくみたいでバブル（泡の）ソートと呼ばれてるようです。

配列の全部を必ずソートするためには、「配列の数 - 1」回実行すれば良いです。

つまり、外側の for 文をかいて、全ての昇順が終わるまでループ実行してあげればＯＫです。

　すこし効率アップ

bubble sort では、内側の for 文を 1 度実行すれば、必ず一番大きな数が一番右側の配列の中に入ります。

2 度実行すれば、2番目に大きな数が右から 2 番目の配列の中に入ります。

このとき、2 度目に実行するときは一番最後の配列にはすでに最大の値が入っているので、要素の比較と並び替えは不要ですね。

n 回実行しているとき、既に、配列の右側 n 個ぶんは昇順ソート済みですので、その分の大小比較の回数は減らすことが出来ます。

bubblesort.c

int main() {
    int score[LENGTH] = { 35, 8, 2, 18, 3 };

    // score 配列を Bubble Sort する
    for (int i = 0; i < LENGTH - 1; i++) {
        for (int j = 0; j < LENGTH - i - 1; j++) {
            if (score[j] > score[j + 1]) {
                swap(&score[j], &score[j + 1]);
            }
        }
    }

このように内側の for 文でループする数をLENGTH - 1 回から、LENGTH - i - 1 回に減らして大丈夫です。

降順のソート

例として作成したプログラムは昇順で配列を並べなおすプログラムでした。このプログラムを降順にするには、隣り合った要素の大小の比較をする演算子を逆にします。

つまり、隣り合う要素同士（ score[j] と score[j+1] を比較して、右側の要素の方が左側の要素よりも大きい時、二つの要素の中身を交換（swap）するようにします。

降順に書き換えた場合のプログラムは下のようになります。

bubblesort.c

int main() {
    int score[LENGTH] = { 35, 8, 2, 18, 3 };

    // score 配列を Bubble Sort する
    for (int i = 0; i < LENGTH - 1; i++) {
        for (int j = 0; j < LENGTH - i - 1; j++) {
            if (score[j] < score[j + 1]) {
                swap(&score[j], &score[j + 1]);
            }
        }
    }