挿入ソート(Insert Sort)とは ~図解や実装例でわかりやすく解説~

f:id:MDaiki:20211209223020j:plain

挿入ソートとは

挿入ソートとは, ソートされていない値をソートされている並びの適切な位置に挿入していくことで, 昇順または降順に並べ替えるアルゴリズムです.

アルゴリズム

insertionSort(Array, N)
    for i が 1からN-1まで
        var = Array[i]
        j = i - 1
        while j >=0 かつ Array[j] > var
            A[j+1] = A[j]
            j--
        A[j+1] = var
変数 説明
Array[N] サイズNの整数型配列
i 未ソートの部分列の先頭を示すループ変数
var Array[i]の値を一時的に保持しておくための変数
j ソート済み部分列からvarを挿入するための位置を探すループ変数

図解

配列 {4, 7, 3, 7, 2, 9}に対して選択ソートを行う. f:id:MDaiki:20211015110725p:plain

未ソート部分(黒のバーより右)から最小の値②を見つける. 次に,最小の値②と未ソート部分の先頭④を入れ替える, f:id:MDaiki:20211015111214p:plain

未ソート部分の先頭の黒のバーの位置を右に1つずらす. 未ソート部分から最小の値③を見つける. 次に,最小の値③と未ソート部分の先頭⑦を入れ替える, f:id:MDaiki:20211015111411p:plain

未ソート部分の先頭の黒のバーの位置を右に1つずらす. 未ソート部分から最小の値④を見つける. 次に,最小の値④と未ソート部分の先頭⑦を入れ替える, f:id:MDaiki:20211015111702p:plain

未ソート部分の先頭の黒のバーの位置を右に1つずらす. f:id:MDaiki:20211015111926p:plain 最小の値が未ソート部分の先頭にいるので何もしない.

未ソート部分の先頭の黒のバーの位置を右に1つずらす. f:id:MDaiki:20211015112202p:plain 最小の値が未ソート部分の先頭にいるので何もしない.

終了

計算量

 
データ数Nとすると最小値を求めるために,  N-1回, N-2回, N-3回...1回と比較演算を行う. そのため,  O(N^2)となる.

C++での実装例

問題

長さNの整数型の数列Aが与えられます. 挿入ソートで昇順で並べ替えなさい.

Sample Input

5
2 3 8 4 2

Sample Output

2 2 3 4 8

Answer

#include <iostream>

void insertionSort(int A[], int N) {
    for(int i = 1; i < N; i++){
        int v = A[i];
        int j = i -1; 

        while(j >= 0 && A[j] > v){
            A[j+1] = A[j];
            j--; 
        }
        A[j+1] = v;
    }
}

int main() {
    int N;
    std::cin >> N;
    int A[N];
    for(int i = 0; i < N; i++){
        std::cin >> A[i];
    }
    insertionSort(A,N);
}

資料

google slideで資料も作ったのでよかったらこちらも参考に!! Google Slide : 選択ソート