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

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

## 自己紹介
- 所属
> **九州工業大学情報工学部**
- ハンドルネーム
> **buridaikon**

## 使わせていただいた問題
https://algo-method.com/tasks/441

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

### コード
```c: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;
}
```

```cpp: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言語で解説）
　このコードの中で挿入ソートを行っているのは次の部分です。一見イメージをしにくいかと思います。

 ```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番目の要素を移動させる）処理をしています。

![GetAttachmentThumbnail.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3618170/74a9b3cc-b622-df24-9e40-808f0c346350.jpeg)

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

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

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