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

トップページ – アルゴリズムとデータ構造編 – 【整列アルゴリズム】第３章

問題① 🔗

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

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

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


= が加わると、比較する２つの要素の値が同じときにも交換が行われることになります。この結果、安定なソートでなくなってしまいます。

あえて安定性をなくす理由はないので、このような実装はしないようにしましょう。

問題② 🔗

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


次のように修正します。

/*
    修正版バブルソート (昇順)
*/
void bubble_sort_ex(int* array, size_t size)
{
    for( size_t i = 0; i < size - 1; ++i ){
        bool flag = false;

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

        // この周回で１度も交換が起きなければ、もうソートできている
        if( !flag ){
            break;
        }
    }
}

新たな変数flag を追加し、外側のループの先頭で false で初期化します。もし、交換処理が行われたら、この変数に true を代入しておきます。

あとは、外側のループの末尾でこの変数をチェックして、false のままだったら、交換が１度も行われなかったことになるので、外側のループから抜け出して、ソート作業を終了させます。

パフォーマンスを測定しておきましょう。

#include <stdbool.h>
#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 bubble_sort(int* array, size_t size);
static void bubble_sort_ex(int* array, size_t size);

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


    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");

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

    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 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 bubble_sort_ex(int* array, size_t size)
{
    for( size_t i = 0; i < size - 1; ++i ){
        bool flag = false;

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

        // この周回で１度も交換が起きなければ、もうソートできている
        if( !flag ){
            break;
        }
    }
}

実行結果：

bubble_sort: 0.296000 seconds
bubble_sort_ex: 0.256000 seconds

大した差は出ていませんが、一応の効率向上はできているようです。ただし、ここでは配列の内容が固定されていますから、もっといろいろなパターンを調べてみるべきです。途中でソート作業を打ち切れず、最後まで繰り返された場合は、追加された処理の影響によって、むしろ性能は落ちることが想像できます。


参考リンク 🔗


更新履歴 🔗

　SIZE_OF_ARRAYマクロの定義を修正。

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

≪さらに古い更新履歴≫

　問題②のプログラムで、コンパイルエラーが起きていたのを修正。

　コードライブラリのパス変更に伴い、リンクを修正。

　新規作成。


第３章のメインページへ

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

Programming Place Plus のトップページへ

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