配列内の数値を整列させる_3（挿入法）

2023年2月13日 2023年2月13日

gifu_shino.g

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

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

1.最初は、配列要素全体が未整列要素です。
　この先頭要素を整列確定要素とします。
2.確定要素の末尾の次の要素（未整列要素の先頭）を
　確定要素の末尾から先頭に向かって順に比較します。
3.比較結果が、確定要素＞未整列の先頭要素
　の間は、その前の確定要素へと比較を進めます。
4.比較結果が、確定要素＜未整列の先頭要素
　となった位置の１つ後方の位置が、未整列先頭要素の
　適切な挿入位置となります。
5.位置が確定し挿入する場合、その位置に空き
　領域を用意する必要があります。
　空き領域の確保には、挿入位置から整列済み
　末尾までの要素の値を、１要素分後ろにずらします。
　※この１要素分をずらす方法として、
　　・3.の比較時に比較しながら後ろにずらす。
　　・4.の挿入位置が確定した時点でまとめてずらす。
　　のどちらかになります。
6.確保できた空き領域に、未整列の先頭要素を
　写します。
7.比較に使用した未整列の先頭要素の位置までを
　整列確定要素とし、2.の操作から処理を繰り返します。
8.未整列要素が無くなった（配列要素の末尾まで
　整列済みとなった）時点で整列操作は完了です。

この解説を図にしてみました。
　※この図では、比較時に後方へずらす処理を行っています。

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

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

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

　プログラムの記述内容

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

#include <iostream>

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

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

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

    // その値の正規位置を探しながらの入替ループ
    for (int head = 1; head < num; head++) {
        work = array[head];
        for (index = head - 1; index >= 0 && array[index] > work; index--) {
            array[index + 1] = array[index];
        }
        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;
　　　　未整列の先頭要素（未整列側の比較対象要素）の仮置き用変数

　　　　※後方へずらす場合に、この要素位置を使用するためです。
　　　int index;
　　　　確定済み配列要素の比較位置を格納するための変数

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

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

　　・その値の正規位置を探しながらの入替ループ
　　　for (int head = 1; head < num; head++) {
　　　　未整列配列の比較対象位置を１つずつ後方へずらしながらのループ

　　　　　work = array[head];
　　　　　　未整列の先頭要素（整列させる）値を仮置きします。

　　　　　for (index = head - 1; index >= 0 && array[index] > work; index--) {
　　　　　　整列済み配列を末尾から先頭に向かって比較するループ

　　　　　　　array[index + 1] = array[index];
　　　　　　　　比較した結果、確定要素の比較対象 ＞ 未整列要素の比較対象の場合、
　　　　　　　　その確定要素側の比較対象要素の値を１つ後方へずらします。
　　　　　　　　※最初の比較での後方位置は、未整列配列の先頭位置となります。

　　　　　}
　　　　　array[index + 1] = work;
　　　　　　比較した結果、確定要素の比較対象 ＜ 未整列要素の比較対象の場合、
　　　　　　その未整列要素側の比較対象要素の値を１つ後方位置に複写します。
　　　　　　※この複写位置は、元の値は後方に移されているので、空き領域となっています。

　　　}

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

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