Thinkers'Studio
JavaとC言語の自習ツール
バブルソートのプログラム例とソートの様子

 いろいろなソート・アルゴリズムがありますが、今回は基本的なものとして知られているバブルソート(隣接交換法)のサンプルプログラムです。 配列要素が 5個だけの簡単な例で、ソートの様子を見てみましょう。

バブルソートのプログラム例 】 (チェック用のプリントを青文字にしています)
#include <stdio.h>

void prtData( int data[], int n )
{
    int i;

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

void bubbleSort( int dt[], int n )
{
    int i, j, temp;

    for( i = 0; i < n-1; i++ ) {
        for( j = n-1; j > i; j-- ) {
            if( dt[j-1] > dt[j] ) {
                printf( "i:%d) %d と %d を交換", i, dt[j-1], dt[j] );
                temp = dt[j];
                dt[j] = dt[j-1];
                dt[j-1] = temp;
                printf( " --> " ); prtData( dt, n );
            }
        }
    printf( "%d回目 比較交換終了時 ", i+1 ); prtData( dt, n );
    }
}

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

    printf( "ソート前 " ); prtData( data, 5 );
    bubbleSort( data, 5 );
    printf( "ソート後 " ); prtData( data, 5 );
}
実行結果
ソート前 5 4 1 6 2
i:0) 6 と 2 を交換 --> 5 4 1 2 6
i:0) 4 と 1 を交換 --> 5 1 4 2 6
i:0) 5 と 1 を交換 --> 1 5 4 2 6
1回目 比較交換終了時 1 5 4 2 6
i:1) 4 と 2 を交換 --> 1 5 2 4 6
i:1) 5 と 2 を交換 --> 1 2 5 4 6
2回目 比較交換終了時 1 2 5 4 6
i:2) 5 と 4 を交換 --> 1 2 4 5 6
3回目 比較交換終了時 1 2 4 5 6
4回目 比較交換終了時 1 2 4 5 6
ソート後 1 2 4 5 6

バブルソートの考え方

 データの後ろから隣り合う2要素を比べ、大小が逆なら入れ替えます。
バブルソート
先頭要素までそれを繰り返すと、データの先頭に一番小さい値が来ることになります(1回目の走査で先頭要素が確定)。上の実行結果では、次の状態です。
1回目 比較交換終了時 1 5 4 2 6
 まだ、先頭要素が決まっただけですから、また後ろから隣り合う2要素の比較、交換を行います。 これで次に小さい値が決まります(2回目の走査で2番目の要素が確定)。
2回目 比較交換終了時 1 2 5 4 6
 このようにして比較と交換を繰り返すと、値が小さいものから順に並びます(データ個数-1回の走査で全要素の場所が確定)。
 泡(バブル)が浮かんでいくように、小さい値がどんどん配列の前の方に移動するので、バブルソートと名づけられたようです。

バブルソートプログラムのループ

 2つのループを使って操作します。
    for( i = 0; i < n-1; i++ ) {  //データ個数-1 回だけ比較交換
        for( j = n-1; j > i; j-- ) {  //j は配列の添字

(今回のクイズです)
 上記バブルソートの処理量のオーダは、次のうちどれで表わされるでしょうか?
 (1) O(N) --- Nに比例する, (2) O(logN) --- 対数に比例する, (3) O(N2) --- Nの2乗に比例する
   (答えは、次回のC言語の Tips で ・・・)
前回のクイズの答え: (前回の問題を見る
  %[A-Z] は 「A-Z の並び」という指定なので、答えは (2)