バブルソートとは？アルゴリズムをフローチャートも使って解説

「ソートアルゴリズム」の一つで、数字の並び方を変える方法です。

ここでは、アルゴリズムを１から説明していき、フローチャートも使って、理解しやすい解説を目指します。

バブルソートとは

並んでいる数字の大小を比較して、大きい順もしくは小さい順に並び替える手法の一つです。

他にも「選択ソート」や「挿入ソート」などがあります。

ソーティングには大きく２通りの方法があり、

• 基数ソーティング
• 比較に基づくソーティング

です。

バブルソートは比較をするので、比較に基づくソーティングの一種になります。

アルゴリズム

ここでは、横一列に並んでいる数字を対象として考えます。

左から順に一番右まで比較していきます。

「21」が3列目までいくと、「50」と比較します。

しかし、「50」の方が大きいので交換はしません。

4列目の「50」と5列目の「2」を比較して「50」の方が大きいので一番右側まで来ます。

つまり、この横一列の数字の中で一番大きいのは「50」ということがわかりました。

あとは同じように1列目から4列目までを比較していきます。

このように比較を1週するごとに大きい順から数字が決まっていきます。

フローチャートとプログラムの例

バブルソートをフローチャートを用いて表現すると以下のようになります。

ループを二重にすることによって、数字の交換と何週も繰り返していくことを可能としています。

このフローチャートを参考にしながらプログラムを作ってみると以下になります。

#include <stdio.h>

int main(void) {
    FILE *fp;
    int n,s,h;
    int i=0;
    int k[100];
    if((fp=fopen("numbers.dat","r"))==NULL)
        printf("ファイルを開けませんでした\n");
    else{
        while(fscanf(fp,"%d",&n)==1){
            k[i]=n;
            i++;
    }//初期状態
        for(s=i;s>0;s--){//範囲内交換の回数
            for(h=0;h<s-1;h++){//範囲内で交換
                if(k[h]>k[h+1]){//二つの値を比較して大小が反対なら入れ替え
                    n=k[h];
                    k[h]=k[h+1];
                    k[h+1]=n;
                }
            }
        }
            printf("バブルソートでソートすると、\n");
        for(s=0;s<i;s++){
            printf("%d\n",k[s]);
        }
        fclose(fp);
    }

    return 0;
}

「numbers.dat」では数字を並べたファイルにします。

例えば、「30,20,43,546,21,1」などです。

読み込んだ数字を「配列k」に入れ、その中でバブルソートをします。

まとめ

今回は、バブルソートについて解説しました。

ソートアルゴリズムの一つであり、数字の並びを変える手法です。

比較的簡単な内容なので、しっかり理解しておきましょう。