Nodachisoft Nodachi Sword Icon
  
@あまじ✎ 2021年3月5日に更新

第2章49 ソートの仕組み(バブルソート)

イチからゲーム作りで覚えるC言語
第2章48 共用体(union)を使う : PREV
NEXT : 第2章50 列挙型(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 文をかいて、全ての昇順が終わるまでループ実行してあげればOKです。

 すこし効率アップ

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]);
            }
        }
    }

ソートする量と実行速度について

バブルソートを使うと簡単に昇順、降順でソートすることが出来ます。

ただ、バブルソートの欠点として、並び替えするデータ量が多いとき、 データの多さに比例してソートにかかる時間が非常に多くなってしまう点があります。

このようなソートをするデータ量と、処理にかかる時間の関係はオーダと呼ばれます。

今回のプログラムではデータ量が n 個に対して、for文で2回囲んで処理しており、 ( n - 1 ) × ( n - i - 1 ) 回の処理をしています。

n の数が増えてくると、n の 2 乗ぶんだけソートにかかる処理の数が増えてきます。

このような場合、オーダは O(N2) と表記されます。

計算方法はさておき、自分が使おうとするデータ処理のアルゴリズムのオーダがいくつなのかの見方がわかることが重要です。

特に3Dの地形を生成するなど、巨大なマップを生成したりデータをループで編集するプログラム作成時、オーダが O(N3) などであれば、 マップが大きくなるにつれ、処理が非常に重たいものになってしまいます。

C言語の標準ライブラリのソート

今回は動きを確認するため、自作でのバブルソートプログラムを作成しましたが、 通常は、プログラミング言語の標準ライブラリに高速でソートできるような関数や機能が 用意されていることが多いです。

C言語の標準ライブラリにも qsort と呼ばれる関数がありますので、次回はそちらを使用した ソート方法について確認していきます。

参考

イチからゲーム作りで覚えるC言語
第2章48 共用体(union)を使う : PREV
NEXT : 第2章50 列挙型(enum)を扱う :
 
 
送信しました!

コメント、ありがとうございます。

なんかエラーでした

ごめんなさい。エラーでうまく送信できませんでした。ご迷惑をおかけします。しばらくおいてから再度送信を試していただくか、以下から DM などでご連絡頂ければと思います。

Twitter:@NodachiSoft_jp
お名前:
 
連絡先:
 
メッセージ:
 
戻る
内容の確認!

以下の内容でコメントを送信します。よろしければ、「送信」を押してください。修正する場合は「戻る」を押してください

お名前:
 
連絡先:
 
メッセージ:
 
Roboto からの操作ではないという確認のため確認キーを入れてください。
確認キー=95
戻る
 / 
送信確認へ
コメント欄
コメント送信確認へ

関連ありそうな記事(5件)です!

第1章01 Visual Studio Community 2019 のインストール手順

#C11仕様#C言語#ゲームプログラミング✎ 2021-08-08
C言語でプログラミングをするために、無料で使える Visual Studio Community を使った開発環境を揃えていく手順や注意点をお話しています。
目次
第2章49 ソートの仕組み(バブルソート)
第2章49 ソートの仕組み(バブルソート)
概要
概要
昇順と降順
昇順と降順
スコアのソート
スコアのソート
コードの確認
コードの確認
降順のソート
降順のソート
ソートする量と実行速度について
ソートする量と実行速度について
C言語の標準ライブラリのソート
C言語の標準ライブラリのソート
参考
参考
Nodachisoft © 2021