アルゴリズムとデータ構造編【整列】 第3章 バブルソート

先頭へ戻る

この章の概要

この章の概要です。

バブルソート

この章では、バブルソートを取り上げます。

隣接交換法や基本交換法と呼ばれることもあります。

バブルソートは、全ての要素に対して、隣接する2つの要素を比較して、大小関係が逆になっていたら交換することを繰り返します。この過程を、要素数-1回行うと、ソートが完了します

詳しい手順を見ていきましょう。

int array[] = {7, 2, 4, 5, 1, 6};

この配列を昇順にソートします。

まず、array[0] と array[1] を比較します。昇順になっていないので交換します。

{2, 7, 4, 5, 1, 6};

次は、array[1] と array[2] を比較し、ここでも交換を行います。

{2, 4, 7, 5, 1, 6};

次は、array[2] と array[3] です。ここでも交換を行います。

{2, 4, 5, 7, 1, 6};

次は、array[3] と array[4] です。ここでも交換を行います。

{2, 4, 5, 1, 7, 6};

次は、array[4] と array[5] です。ここでも交換を行います。

{2, 4, 5, 1, 6, 7};

配列の末尾まで行き着きました。実はこの時点で、末尾に来た 7 の位置は確定できています。ここまでに、元々、配列の先頭にあった 7 が、1つずつ移動してきたことが分かると思います。配列を、次のように縦書きにすると、

7
6
1
5
4
2

最初、一番下にあった 7 が、1つずつ上へ上へと浮き上がってきたように見えることから、バブルソート(バブルは泡のこと)と呼ばれます。

さて、ここまでを1回として、要素数 -1回繰り返します。最初に戻って array[0] と array[1] を比較します。2 と 4 なので交換は起きません。

array[1] と array[2] は、4 と 5 なので交換しません。array[2] と array[3] は、5 と 1 なので交換します。

{2, 4, 1, 5, 6, 7};

array[3] と array[4] は、5 と 6 なので交換しません。array[5] は確定済みなので、array[4] と array[5] は比較すら行わず、この回の処理は完了です。array[4] は 6 で確定しました。

再び、先頭に戻ります。array[0] と array[1] は、2 と 4 なので交換しません。array[1] と array[2] は、4 と 1 なので交換します。

{2, 1, 4, 5, 6, 7};

array[2] と array[3] は、4 と 5 なので交換しません。この回はここで終わりです。array[3] は 5 で確定しました。

再び、先頭に戻ります。array[0] と array[1] は、2 と 1 なので交換します。

{1, 2, 4, 5, 6, 7};

array[1] と array[2] は、2 と 4 なので交換しません。この回はここで終わりです。array[2] は 4 で確定しました。

再び、先頭に戻ります。array[0] と array[1] は、1 と 2 なので交換しません。array[2] は確定済みなので、この回も終わりです。array[1] と array[0] はこれにて確定します。


プログラム例

では、先ほどの過程を元に、実際のプログラムを書いてみましょう。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b)          { type work = a; a = b; b = work; }

static void bubble_sort(int* array, size_t size);
static void print_array(const int* array, size_t size);

int main(void)
{
    int array[] = {7, 2, 4, 5, 1, 6};

    print_array( array, SIZE_OF_ARRAY(array) );
    bubble_sort( array, SIZE_OF_ARRAY(array) );
    print_array( array, SIZE_OF_ARRAY(array) );

    return 0;
}

/*
    バブルソート (昇順)
*/
void bubble_sort(int* array, size_t size)
{
    size_t i, j;

    for( i = 0; i < size - 1; ++i ){
        for( j = 1; j < size - i; ++j ){
            if( array[j-1] > array[j] ){
                SWAP(int, array[j-1], array[j]);
            }
        }
    }
}

/*
    配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
    size_t i;

    for( i = 0; i < size; ++i ){
        printf( "%d ", array[i] );
    }
    printf( "\n" );
}

実行結果:

7 2 4 5 1 6
1 2 4 5 6 7

bubble_sort関数がバブルソートを実装した関数です。

外側の for文が、要素数-1回の繰り返しを行うためのループになっています。

内側の for文では、比較する2つの要素のうち、後ろ側の要素を表す添字を制御しています。外側のループ1回ごとに、末尾の要素が確定していくので、添字j の上限値は1つずつ減っていくようになっています。

まとめ

バブルソートの計算量は O(n2) で、遅い整列アルゴリズムだと言えます。なお、バブルソートは安定なアルゴリズムです

計算量からいえば、選択ソート(第2章)と同じですが、通常、選択ソートの方が効率的です。バブルソートの性能は、むしろ単純ソート(第1章)に近いと言えます。

バブルソートの利点は、実装の容易さだと言われていますが、主観では選択ソートの方が分かりやすいようにも思えます。人によると言えばそれまでですが、少なくとも大差はないと思います。そのため、あえてバブルソートを採用する理由はほとんどありません

近年では、並列化しやすいという新たな利点が見出されており、奇偶転置ソートなどの改良型があります。


練習問題

問題① bubble_sort関数内の if文の比較演算子を、

if( array[j-1] >= array[j] )

このように > から >= に変更すると、実行結果にどんな変化が起こりますか?

問題② bubble_sort関数の外側の for文が1周するごとに、その回に1度も交換が起きなければ、まだ要素数-1回の繰り返しが済んでいなくても、ソートを完了させることができます。そのような方法で bubble_sort関数を最適化して下さい。


解答ページはこちら

参考リンク



更新履歴

'2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2012/5/19 新規作成。



前の章へ(第2章 選択ソート)

次の章へ(第4章 挿入ソート)

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ


このエントリーをはてなブックマークに追加
rss1.0 取得ボタン RSS