ロゴ ロゴ

ソーティング基礎勉強会

こんにちは、そしてお久しぶりなじゃた。です。ずいぶん前に「ソーティングを勉強します！」と宣言したのはよかったのですが、それからかなりの期間が…💦まあ、やれば許される！！ということで、さっそくソーティングについてやっていきましょう！！(言語は安定のCです。C++も書けるようになりたい😢)
【今回の目標:ソーティングについての理解を深める！】

ソーティングとは

ソーティングとは、文字通り「並べ替え」のことです。数字や文字を順に並べ替えることを”ソート”といいます。名前の順にするとか、数を大きい順に並べるとかですね。
とりあえず分かりやすい簡単なソートアルゴリズムとして、一番小さな数字を先頭に移動するという処理を繰り返すものを考えましょう。

#include<stdio.h>
int main(void) {
    //数字入力
    int num[5];
    for (int i = 0; i < 5; i++) {
        scanf("%d", &num[i]);
    }

    //ここからソーティング
    int temp;
    for (int i = 0; i < 4; i++) {
        for (int j = i + 1; j < 5; j++) {
            //今比較してる数字よりも小さい数字があったら入れ替え
            if (num[i] > num[j]) {
                temp = num[i];
                num[i] = num[j];
                num[j] = temp;
            }
        }
    }

    printf("\n---並べ替え結果を表示します。---\n");
    for (int i = 0; i < 5; i++) {
        printf("%d\n", num[i]);
    }

    return 0;
}

このプログラムを実行すると、以下のような結果になります。

また、今回の動作を図で表すと以下のようになります。

まずは一番小さい数字を先頭に、次は2番目に小さい数字を先頭から2番目に、というように並べ替えを行っていくわけです。そうすれば最終的に数が小さい順になります。大きい順にするのも同様の方法でできますね。では次に、バブルソートについて考えていきましょう。

バブルソート

バブルソートとは隣のデータと比較して、隣のデータの方が小さければ(大きければ)入れ替えを行うという処理を繰り返し行っていくものです。まるでその動きが泡のようであることからバブルソートと呼ばれるようになったと風のうわさで聞きました。図で表すと以下のようになります。

では、先ほどと同じように5つの数字を入力してその数値を入れ替えるというバブルソートアルゴリズムを以下に示します。

int temp;
for(int i = 0; i < 4; i++){
    for(int j = 0; j < 4 - i; j++){
//隣同士を比較してより小さければ入れ替え
        if (num[j] > num[j + 1]) {
            temp = num[j];
            num[j] = num[j + 1];
            num[j + 1] = temp;
        }
    }
}

当たり前ですが、先に示したソートアルゴリズムでも今回示したバブルソートアルゴリズムでもどちらも結果は同じになります。じゃあ結局どちらの方がいいのでしょうか。同じ結果だとは言っても中身が違うので、結果までの道のりが違います。やはりこういった作業の道のりは短いほうがいいですよね。同じ目的地まで長い道と短い道どちらを選択しますか、ということです。
長い道か短い道かというのは、処理の数を見れば分かりますね。ということで、今回使用した2つのコードについて、比較回数を計算してみたいと思います。データ数をnとすると、先に示したコードでは、

比較回数＝Σk (kは1からn-1まで)＝{n(n-1)}/2=10回

※ “Σ” はシグマです。正しく表示されない場合があるため、注釈をつけさせていただきます。

となります。一方バブルソートを用いたコードでは、

比較回数＝Σk (kは1からn-1まで)＝{n(n-1)}/2=10回

となります。数値化してみれば一目瞭然！のはずですが…。あらら、同じですね😅結局、どちらを使っても変わらないということでしょうか。というのは、私が前にソーティングについて学んだ時にもぶち当たった疑問です。結局、どちらの方がいいのでしょうね。本当にどちらも変わらないのでしょうか…。

まあわからないことを延々と考えていても仕方がないので次へ行きます！今回はデータ数が5つと極めて少ないため、処理数など気にせずとも一瞬で終わるのでどうでもいいのですが、実際に使用する場面では莫大な数のデータ数を扱うことになります。求める動作をするといっても処理数を気にせずにただ突っ走るのは駄目だということです。難しいですね…。

おわりに

膨大なデータの並べ替えを手作業で行うのはやはり時間も無駄だし、ミスも多々でてくるでしょうからプログラムで自動化するのがいいですよね！いやぁ、自動化ってやっぱりすごい！！ソートアルゴリズムはいろんな方が沢山研究していて、今回考えたものよりももっといいものがいっぱいあります。気になる方はぜひ調べてみてください。
今回はソーティングについて軽く学ぼうということでやってみましたが、実際の使い方がわからなかったら面白くないですよね。ということで、次はファイルからデータを読み込んで並べ替えたものを出力する、ということをやっていきたいと思います！お楽しみに！！
では、またの機会に！See You Next Time！

コメント入力

関連サイト