配列内の数値を整列させる_1（選択法）

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

gifu_shino.g

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

選択法の簡単な解説とプログラムしてみます。
※この説明では、昇順に整列させることが前提です。

1.整列対象の未整列配列要素の中から、最小値を探します。
　※最初は、配列要素全体が未整列で対象となります。
2.見つかった最小値と、未整列対象配列の先頭位置の
　値とを入れ替えます。
　※見つかった最小値が、未整列対象配列の先頭位置と
　　同じ位置の場合は、入替を行う必要はありません。
3.未整列対象配列の先頭位置を整列確定として、
　未整列対象配列から外します。
　※これにより、未整列対象配列の先頭位置は、
　　次の要素位置になります。
4.1. 2. 3. の操作を未整列対象配列要素がなくなるまで
　（末尾の要素まで）繰り返します。

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

では、整列_選択法をプログラムしてみます。

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

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

　プログラムの記述内容

// 配列内の数値を整列させる
// 選択法による昇順（降順）

#include <iostream>

int main()
{
    // 変数宣言と初期化
    int array[] = { 5,1,7,6,4,8,2,10,3,9 };
    int num;
    int min_index;
    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 head = 0; head < num - 1; head++) {
        min_index = head;
	// 最小値の探索
        for (int index = head + 1; index < num; index++) {
            if (array[min_index] > array[index]) {
                min_index = index;
            }
        }
	// 最小値の入れ替え
        if (head != min_index) {
            work = array[head];
            array[head] = array[min_index];
            array[min_index] = 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 min_index;
　　　　探索中の最小値の要素位置（要素番号）を格納するための変数
　　　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 head = 0; head < num - 1; head++) {
　　　　外ループは、整列が１つ確定するごとに未整列要素の
　　　　先頭位置を１つずつ後方へ末尾要素の１つ手前までずらします。
　　　　※未整列要素の範囲を設定

　　　　　min_index = head;
　　　　　　未整列配列の先頭要素の位置を最小値の比較対象
　　　　　　位置として仮格納（仮置き）します。

　　　　　for (int index = head + 1; index < num; index++) {
　　　　　　内ループでは未整列配列要素の２番目から仮置き値と比較し、
　　　　　　末尾の要素まで探索し、最小値の位置を確定します。
　　　　　　※未整列要素内で最小値を探索します。

　　　　　　　if (array[min_index] > array[index]) {
　　　　　　　　　min_index = index;
　　　　　　　　仮置き値より小さい値を発見したら、仮置き
　　　　　　　　位置を更新し、最小値位置を更新します。
　　　　　　　　※降順に整列させたい場合には、
　　　　　　　　　"if (array[min_index] > array[index]) {" を
　　　　　　　　　"if (array[min_index] < array[index]) {" と
　　　　　　　　　記述を修正（ "＞" → "＜" ）するたけで可能です。

　　　　　　　}
　　　　　}

　　　　　if (head != min_index) {
　　　　　　　work = array[head];
　　　　　　　array[head] = array[min_index];
　　　　　　　array[min_index] = work;
　　　　　　最小値の位置が、未整列の先頭位置から更新されて
　　　　　　いる場合、その二つの位置の値を入れ替えます。
　　　　　　※これで、未整列配列内の最小値が、未整列配列内の
　　　　　　　先頭位置に設定されます。

　　　　　}
　　　}

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

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