苦しんで覚えるC言語

バブルソート


整列(ソート)とは


整列(ソート)とは、でたらめに並べられたデータを順番通りに並び替えることです。
例えば、次のように並び替えます。
ソート前239715313019
ソート後137915192330
この時、左に行くほど値が小さくなるソートを昇順と呼びます。
反対に、右に行くほど値が小さくなるソートは降順です。

ソートアルゴリズムでは、高速性の他、安定性が必要なことがあります。
安定とは、ソート後に、同じ値のデータの並び順が変化しないことです。

例えば、次はあるクラスの小テストの結果だとします。
野比のび太0
源静香90
剛田武50
骨川スネ夫50
これを安定な方法で並び替えると次のようになります。
野比のび太0
剛田武50
骨川スネ夫50
源静香90
同じ点数である剛田と骨川の前後関係はソートする前と同じです。
次は、非安定な方法で並び替えます。
野比のび太0
骨川スネ夫50
剛田武50
源静香90
同じ点数である剛田と骨川の前後関係が入れ替わっています。
場合によっては、同じ点数の人の並び順を保持する必要があり、
その場合には安定した方法を使わなければなりません。
ソートの目的
もともとでたらめに並んでいたのならそのままにしておけばよいのに、
わざわざそれをソートする理由は、ズバリ検索のためです。
データがそろえられていると、目的の値がどこにあるか見当がつき、
データがでたらめに並んでいる場合よりも素早く検索できます。

目次に戻る

バブルソート


ソートには実に様々なアルゴリズムが考案されていますが、
その中でもバブルソートは、プログラムのわかりやすさからよく取り上げられます。
ただし、速度は遅いため、あまり優秀な方法とはいえません。

その考え方は簡単です。
まず、1つ目と2つ目のデータを比べ、2つ目が小さい場合はデータを交換します。
次は、2つ目と3つ目を比較して交換します。これをデータの最後まで繰り返します。
データの最後まできたら、また1つ目から比較と交換を繰り返します。
これをデータの個数回だけ繰り返せば、データが整列されます。
1つ目と2つ目の比較(23)(9)715313019
2つ目が小さいので交換(9)(23)715313019
2つ目と3つ目の比較9(23)(7)15313019
3つ目が小さいので交換9(7)(23)15313019
以後、これを繰り返す。
バブルソートをプログラムとして実装すると次の通りになります。
使用法
SortBubble(ソートする配列、ソートする個数);

void SortBubble(int array[],int n)
{
    int i,j,temp;

    for (i = 0;i < n - 1;i++) {
        for (j = 0;j < n - 1;j++) {
            if (array[j + 1] < array[j]) {
                temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;
            }
        }
    }
}
動作を確認する場合は、arrayの型をcharとして、文字配列を渡すのが簡単です。

バブルソートでは2重のループを使うため、計算回数は O(N^2) となります。
始めに述べた通り、ソートアルゴリズムとしては低速です。

目次に戻る