配列内の数値を整列させる_2（隣接交換（バブルソート）法）

2023年2月11日 2023年2月11日

gifu_shino.g

配列内の数値を、昇順（降順）に整列してみます。
反復（繰り返し）処理のネスト（入れ子）処理の
基礎として配列内数値の整列がよく説明されています。
この基本的な整列法として、選択法、隣接交換法、挿入法が
あります。

隣接交換（バブルソート）法の簡単な解説とプログラムしてみます。
※この説明では、昇順にすることが前提です。

1.整列対象の未整列配列要素の先頭から順に、
　隣り合う２つの要素値を比較します。
　この時、前要素の値＞後要素の値の関係の場合、
　この２つの要素の値を入れ替えます。
　これを末尾の要素まで繰り返します。
　※要素番号で考えると、
　　0 ? 1、 1 ? 2、 2 ? 3、3 ? 4、・・・・
　　と比較する。
　※最初は、配列要素全体が未整列で対象です。
2.1.の操作により、整列対象の未整列配列要素の
　末尾に最大値が設定されます。
　この末尾の要素を整列確定済要素として、
　未整列要素から外し、1.の操作を繰り返します。
3.未整列要素が、１要素になった段階（未整列の
　隣接要素がない状態）で整列操作は完了となります。

この解説を図にしてみました。

では、整列_隣接交換（バブルソート）法をプログラムしてみます。

・プロジェクトを作成します。
　Visual Studio 2022を起動し、
　新しいプロジェクトを作成します。
　・プロジェクトタイプ："コンソールアプリ"
　・プロジェクト名："ct_107_2"
　とします。

・プログラム記述・編集画面が表示されるので、
　以下のプログラムを記述します。

　プログラムの記述内容

// 配列内の数値を整列させる
// バブルソート（交換）法による昇順（降順）

#include <iostream>

int main()
{
    // 変数宣言と初期化
    int array[] = { 5,1,7,6,4,8,2,10,3,9 };
    int num;
    int work;

    // array配列の要素数を取得
    num = sizeof(array) / sizeof(array[0]);

    // 整列前の配列内数値の表示
    printf("整列前 :");
    for (int i = 0; i < num; i++) {
        printf("%4d", array[i]);
    }
    printf("\n");

    // 隣り合う数値を比較しながらの入替ループ
    for (int max_index = num - 1; max_index > 0; max_index--) {
        for (int index = 0; index < max_index; index++) {
            if (array[index] > array[index + 1]) {
                work = array[index];
                array[index] = array[index + 1];
                array[index + 1] = work;
            }
        }
    }

    // 整列後の配列内数値の表示
    printf("整列後 :");
    for (int i = 0; i < num; i++) {
        printf("%4d", array[i]);
    }
    printf("\n");

    return EXIT_SUCCESS;
}

　簡単なプログラム解説です。

　　・変数宣言と初期化
　　　int array[] = { 5,1,7,6,4,8,2,10,3,9 };
　　　　整列に使用する未整列値の配列を宣言します。
　　　int num;
　　　　配列の要素数を格納するための変数
　　　int work;
　　　　２つの要素間で値を入れ替える時の仮置き用変数

　　・array配列の要素数を取得
　　　num = sizeof(array) / sizeof(array[0]);
　　　　この式によって、配列内の要素数を取得できます。

　　・整列前の配列内数値の表示
　　　printf("整列前 :");
　　　for (int i = 0; i < num; i++) {
　　　　　printf("%4d", array[i]);
　　　}
　　　printf("\n");
　　　　整列前の要素の値を表示するためのループ処理

　　・隣り合う数値を比較しながらの入替ループ
　　　for (int max_index = num - 1; max_index > 0; max_index--) {
　　　　外ループは、整列が１つ確定するごとに未整列要素の
　　　　末尾位置を１つずつ前方へ先頭要素の１つ後方まで順にずらします。
　　　　※未整列要素の範囲を設定

　　　　for (int index = 0; index < max_index; index++) {
　　　　　内ループは、隣り合う要素同士を比較します。
　　　　　※未整列要素内で大小関係を比較します。

　　　　　　if (array[index] > array[index + 1]) {
　　　　　　　　work = array[index];
　　　　　　　　array[index] = array[index + 1];
　　　　　　　　array[index + 1] = work;
　　　　　　　　　前要素値 ＞ 後要素値の場合、２つの
　　　　　　　　　要素間で値を入れ替えます。
　　　　　　　　　※降順に整列させたい場合には、
　　　　　　　　　　　if (array[index] > array[index + 1]) { を
　　　　　　　　　　　if (array[index] < array[index + 1]) { と
　　　　　　　　　　と記述を修正するたけで可能です。
　　　　　　}
　　　　}
　　}

　　・整列後の配列内数値の表示
　　　printf("整列後 :");
　　　for (int i = 0; i < num; i++) {
　　　　　printf("%4d", array[i]);
　　　}
　　　printf("\n");
　　　　整列後の要素の値を表示するためのループ処理

・実行してみます。
　上段メニュー"デバッグ(D)"のサブメニューより、
　"デバッグなしで開始(H)"を選択します。