バブルソート

アルゴリズムが単純で実装が容易なため、しばしば用いられます。
配列において、隣り合う要素の値を総当たりで比較するため、処理時間はかかりますが、安定な内部ソートを実現します。

アルゴリズム

題意より、常に [i] の値は [i + 1] の値以下となり、最小値は arrray[0] 、最大値はarray[9] に置かれます。

まず、[0]と[1]を比較し、順番が逆であれば位置を交換します。次に、[1]と[2]を比較し、順番が逆であれば位置を交換します。

これを最後まで（ここでは[8]と[9]まで）行うと、最後の数だけが最小または最大の数として確定します。

プログラムソース

array	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
0	1	0	3	2	0	1	2	0	1

array	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
0	0	1	3	2	0	1	2	0	1

array	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
0	0	1	2	0	1	2	0	1	3

array	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
0	0	1	0	1	2	0	1	2	3

array	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
0	0	1	0	1	0	1	2	2	3

array	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
0	0	0	0	1	1	1	2	2	3

　倍精度実数配列に対するソースを示します。ここで、配列の要素数は、配列の定義等によって既知であるとします。
　数値配列に対する汎用性を考慮しており、このまま使用する場合は、引数にあたる配列のデータ型をキャストしてください。

/* バブルソート（昇順） */
/* array ... ソートを行う配列 */
/* n     ... array の要素数 */

void bubblesort(double array, int n)
{
    int       i, j;    /*繰り返し作業のためのカウンタ*/
    double    temp;    /*値交換の仲介用の変数*/

    for(i = n-1; i > 0 ; i--)
        /*外側ループ: 以下の作業を配列要素の個数分（n回）だけ繰返す（配列の末尾－大きな値－から順序を確定する）*/
    {
        for(j = 0; j < i; j++)
            /*内側ループ: 以下の作業を順序が確定していない要素の個数分だけ繰り返す*/
        {
            if(array[j] > array[j+1])
                /*小さな要素番号の値 > 大きな要素番号の値*/
            {
                /*位置を交換する*/
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

バブルソート

概要

アルゴリズム

プログラムソース

関連項目

更新履歴