ももの知恵の樹

C言語アルゴリズム-バブルソート

バブルソート(Bubble Sort)とは

バブルソートとは、隣り合ってる要素の大小関係を比較して入れ替える、という操作を繰り返す整列アルゴリズムです。

要素が正しい位置に泡のように登っていく様子からバブルソートと呼ばれます。アルゴリズムは単純ですが、無駄な比較が多くて実行速度は遅いため、勉強以外で用いられることはありません。計算量は「O(n^2)」となります。


バブルソート整列の様子

配列の後ろから先頭に向かってスキャンしていき、隣り合う２つの要素の大小関係が逆である場合、要素を入れ替えます。 


[before]:2 6 3 4 1 5 
---------[1 round]---------
2 6 3 4 1 5 
2 6 3 1 4 5 
2 6 1 3 4 5 
2 1 6 3 4 5 
1 2 6 3 4 5 
---------[2 round]---------
1 2 6 3 4 5 
1 2 6 3 4 5 
1 2 3 6 4 5 
1 2 3 6 4 5 
---------[3 round]---------
1 2 3 6 4 5 
1 2 3 4 6 5 
1 2 3 4 6 5 
---------[4 round]---------
1 2 3 4 5 6 
1 2 3 4 5 6 
[after]:1 2 3 4 5 6

C言語によるバブルソートのプログラム

数値配列の整列を行います。 


#include <stdio.h>

static void
array_print(int *array, unsigned int size)
{
    int i = 0;

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

/*!
 * @brief   バブルソート整列を行う。
 * @param[in/out]  array  整列する要素配列
 * @param[in]      size   配列のサイズ
 */
void
bubble_sort(int *array, unsigned int size){
    int i, j, t;
    for(i = 0; i < size - 1; i++){
        printf("---------[%d round]---------\n", i + 1);
        for(j = size - 1; j > i; j--){
            if (array[j] < array[j - 1]){
                t = array[j];
                array[j] = array[j - 1];
                array[j - 1] = t;
            }
            array_print(array, size);
        }
    }
}

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

    printf("[before]:");
    array_print(data, sizeof(data)/4);

    bubble_sort(data, sizeof(data)/4);

    printf("[after]:");
    array_print(data, sizeof(data)/4);

    return(0);
}

関連ページ