挿入ソート C/C++（備忘録）

はじめに

　今回の記事は挿入ソートを学習した備忘録として書いたものである。
ど素人なので間違っていることが多いです。ご指摘いただければ幸い
です。

自己紹介

• 所属

九州工業大学情報工学部

• ハンドルネーム

buridaikon

使わせていただいた問題

内容

挿入ソートって？

　ソートされていない要素を配列の適切な位置に挿入してソートするアルゴリズムのこと

コード

C言語

// 挿入ソート

#include <stdio.h>

void input(int array[], int n)
{
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &array[i]);
    }
}

void output(int array[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        printf("%d", array[i]);
        printf(" ");
    }

    printf("%d\n", array[n - 1]);
}

int main(void)
{
    int n; // 整数型変数nを宣言
    scanf("%d", &n); // nに値を入力

    int array[n]; // 要素数nの整数型配列arrayを宣言

    input(array, n); // 作成したinput関数で配列arrayに入力

    for (int i = 1; i < n; i++) // 挿入ソートの部分
    {
        int position = i; // 調べ始める場所（要素のアドレス）をiとする

        while (position != 0 && array[position - 1] > array[position])
        {
            int empty = array[position - 1];
            array[position - 1] = array[position];
            array[position] = empty;
            position--; // positionをデクリメント
        }

        output(array, n); // １回分のソートが終わるたびにoutput関数で出力（改行込み）
    }

    return 0;
}

C++

// 挿入ソート
#include <bits/stdc++.h>

using namespace std;

void input(vector<int> &vec, int n) // 配列にデータを入力するための関数inputを作成
{
    for (int i = 0; i < n; i++) // 入力
    {
        cin >> vec[i];
    }
}

void output(vector<int> &vec, int n) // ソート後の配列のデータを出力するための関数outputを作成
{
    for (int i = 0; i < n - 1; i++) // 出力（末尾以外スペース込みで）
    {
        cout << vec[i] << " ";
    }

    cout << vec[n - 1] << endl; // 末尾の要素を出力して改行
}

int main() // main関数
{
    int n; // 繰り返し回数用の整数型変数nを宣言
    cin >> n; // nに入力
    vector<int> vec(n); // 動的配列vecを宣言（要素数はn）
    input(vec, n); // 作成したinput関数を使ってvecに入力

    for (int i = 1; i < n; i++) // 挿入ソート（全ての要素で調べる（positionの初期値を1とするために、iの初期値も1とする）
    {
        int position = i; // 整数型変数positionを宣言してiを代入

        while (position != 0 && vec[position - 1] > vec[position]) // 選択範囲を狭めながら挿入個所を探す（手前から奥に迫るイメージ）
        {
            swap(vec[position - 1], vec[position]); // 要素の入れ替え
            position--; // positionをデクリメント
        }

        output(vec, n); // 作成したoutput関数で動的配列の現時点での中身を出力
    }

    return 0; // 終了
}

挿入ソートの詳しい説明（C言語で解説）

　このコードの中で挿入ソートを行っているのは次の部分です。一見イメージをしにくいかと思います。

for (int i = 1; i < n; i++)
   {
       int position = i;

       while (position != 0 && array[position - 1] > array[position])
       {
           int empty = array[position - 1];
           array[position - 1] = array[position];
           array[position] = empty;
           position--;
       }
       output(array, n);
   }

例えば、要素数を5、入力する配列を3 1 4 2 5とします。
実際にプログラムで求めてみると、

入力

3 1 4 2 5

出力

1 3 4 2 5
1 3 4 2 5
1 2 3 4 5
1 2 3 4 5

考え方としては、i番目の要素から比較が始まり、どんどん奥から手前に迫ってきて、最終的に一番先頭の要素まで並べ替える（適切な位置にi番目の要素を移動させる）処理をしています。

簡単にトランジションを説明すると上図のようになります。

図にはすべては書いていませんが、4回のすべてのループにおいて、i番目から0番目まで移動しながら入れ替え（i番目の要素の移動）を行っていることを意識してみてください。
、、、とは言ったものの！
条件式を見ても分かりますが、入れ替えができなかったら（調べている途中でposition番目よりもposition-1番目が小さかったら）whileを抜けて、先頭まで調べることなく次回のソートに移ります（それ故に速い）

駄文をここまで読んでいただきありがとうございました！