バブルソート | Programming Place Plus　アルゴリズムとデータ構造編【整列アルゴリズム】　第３章

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

この章の概要 🔗

この章の概要です。


バブルソート 🔗

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

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

バブルソートは、データ列の先頭から順に、隣接する２つの要素を比較して、大小関係が逆になっていたら交換することを末尾まで繰り返し行います。

単純ソート（第１章）と似ていますが、比較するたびに、比較の基準になる側の位置も変えていくところが異なります。またこれに絡んで、周回のたびに、データ列の先頭に戻る点にも違いがあります。

たとえば、対象のデータ列が次のような配列だとします。

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 が、１つずつ移動してきたことが分かると思います。配列を、次のように縦書きにすると、

7
6
1
5
4
2

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


ここまでを１周目として、この過程を「要素数 - 1」回だけ繰り返します。最初に戻って array[0] と array[1] を比較します。周回ごとに array[0] からやりなおす必要があります。ここが単純ソートとの違いの２つ目です。

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] ともに確定となって、バブルソートの全工程が終了しました。


バブルソートは単純ソートよりはやや効率が良くなっています。とはいえ、最大で要素数分のループを二重に行うかたちは変わらないので、計算量としては変わらず O(n2) です。

プログラム例 🔗

それでは、冒頭で確認した実行過程を踏まえて、バブルソートのプログラムを書いてみましょう。

#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)
{
    for( size_t i = 0; i < size - 1; ++i ){
        for( size_t 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)
{
    for( size_t 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文では、比較する２つの要素のうち、後ろ側の要素を表す添字 j を制御しています。この for文の繰り返し条件は j < size - i です。最後の部分は「- 1」ではなく「- i」であることに注意してください。外側の for文が１周するたびに、末尾から要素が１つ確定するのですから、そのつど、内側の for文で参照する要素は１つずつ減っていくためです。

性能 🔗

第１章、第２章であつかった単純ソート、選択ソートと、今回のバブルソートはいずれも、計算量としては O(n2) です。

様々な要因に左右されるものの、実際には、選択ソートが一番速く、単純ソートが一番遅くなります。

実際に、それぞれの性能比較をしてみます。

#include <stdio.h>
#include <stdlib.h>
#include "ppp_perform.h"

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

static void init_array(int* array, size_t size);
static void simple_sort(int* array, size_t size);
static void selection_sort(int* array, size_t size);
static void bubble_sort(int* array, size_t size);

int main(void)
{
    int array[ARRAY_SIZE];


    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    simple_sort( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("simple_sort");

    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    selection_sort( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("selection_sort");

    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    bubble_sort( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("bubble_sort");

    return 0;
}

/*
    配列を初期化
*/
void init_array(int* array, size_t size)
{
    srand(0);

    for( size_t i = 0; i < size; ++i ){
        array[i] = rand() % size;
    }
}

/*
    単純ソート (昇順)
*/
void simple_sort(int* array, size_t size)
{
    for( size_t i = 0; i < size - 1; ++i ){
        for( size_t j = i + 1; j < size; ++j ){
            if( array[i] > array[j] ){
                SWAP(int, array[i], array[j]);
            }
        }
    }
}

/*
    選択ソート (昇順)
*/
void selection_sort(int* array, size_t size)
{
    for( size_t i = 0; i < size - 1; ++i ){

        // 第 i 位となる値の位置を探す
        size_t min_index = i;
        for( size_t j = i + 1; j < size; ++j ){
            if( array[min_index] > array[j] ){
                min_index = j;
            }
        }

        // 第 i 位の値をもつ要素と、array[i] を交換する
        SWAP(int, array[i], array[min_index]);
    }
}

/*
    バブルソート (昇順)
*/
void bubble_sort(int* array, size_t size)
{
    for( size_t i = 0; i < size - 1; ++i ){
        for( size_t j = 1; j < size - i; ++j ){
            if( array[j-1] > array[j] ){
                SWAP(int, array[j-1], array[j]);
            }
        }
    }
}

実行結果：

simple_sort: 0.322000 seconds
selection_sort: 0.115000 seconds
bubble_sort: 0.257000 seconds

まとめ 🔗

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

バブルソートは安定なアルゴリズムです。

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

バブルソートの利点は、実装の容易さだと言われていますが、主観では選択ソートと大差ないように思えます。あえてバブルソートを採用する理由はほとんどないでしょう。

【上級】並列化しやすいという利点が見出されており、奇偶転置ソートなどの改良型があります。


練習問題 🔗

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

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

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

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


解答ページはこちら。

参考リンク 🔗


更新履歴 🔗

　SIZE_OF_ARRAYマクロの定義を修正。

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

　新規作成。


前の章へ　（第２章　選択ソート）

次の章へ　（第４章　挿入ソート）

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

Programming Place Plus のトップページへ

はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポスト／フォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る