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

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

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

バブルソートとは
アルゴリズム
フローチャートとプログラムの例
まとめ

バブルソートとは

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

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

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

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

です。

2通りの方法

基数ソーティング：要素の大きさから位置を決める。

比較に基づくソーティング：要素の大小比較を行い、位置の入れ替えをする。

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

アルゴリズム

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

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

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

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

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

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

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

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

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

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

フローチャートについて学びたい方はこちら！

Processing入門｜条件分岐について解説｜if、switch文編

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

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

#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」に入れ、その中でバブルソートをします。