C++で実装する初等的ソートアルゴリズム１【挿入ソート】

最近プロコンのためにアルゴリズムの勉強始めたので、メモを残しておきます。まずは基本であるソートをやっていこうかと。今回は挿入ソートです。

目標

挿入ソートを理解する。プロコンの問題を解くことで実装も行う。

挿入ソート

挿入ソートは初等的なソートアルゴリズムの一つで、計算量は $O(N^2)$ 。もともと昇順に並んでいる場合は、 $O(N)$ で済むという特徴があります。

手順

先頭の要素をソート済み部分とする。
未ソート部分がなくなるまで、以下を繰り返す：
1. 未ソート部分先頭から要素を取り出し、変数（vとする）に格納。
2. ソート済み部分のうち、vより大きい要素を後方に移動する。
3. 最後に空いた位置にvを挿入。

未ソート部分の先頭を、ソート部分の適切の適切な位置に埋め込んでいくことで、ソート済み部分を後方に拡大していくようなイメージ。

問題を解いてみる

Aizu Online Judgeの問題を解いてみました。言語はc++です。
Insertion Sort | Aizu Online Judge

解答例：

#include<iostream>
using namespace std;

// 数列を表示する関数
void display(int seq[], int N) {
  int i;
  for (i = 0; i < N; i++) {
    if (i > 0) cout << " ";
    cout << seq[i];
  }
  cout << endl;
}

int main() {
  int i, j, v, N;
  int seq[100];  // 数列

  cin >> N;
  for (i = 0; i < N; i++) {
    cin >> seq[i];
  }

  display(seq, N);

  // sort
  for (i = 1; i < N; i++) {  // 1から始まることに注意
    v = seq[i];  // 未ソート先頭部分を一時的に格納
    j = i - 1;    
    while (j >= 0 && seq[j] > v) {
      seq[j+1] = seq[j];
      j--;
    }
    seq[j+1] = v;
    display(seq, N);
  }
      
  return 0;
}