C++による挿入ソート

挿入ソートとは

挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n²)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。

挿入ソートを高速化したソート法として、シェルソートが知られている。

挿入ソート – Wikipedia より

C++による実装

#include <iostream>

using namespace std; 

int main() {
  int key;
  int i, j, n = 9;
  int arr[] = {6,5,1,10,11,23,30,2,7};

  for (i = 1; i < n; i++) {
    key = arr[i];
    for (j = i; j > 0 && arr[j-1] > key; --j) {
        arr[j] = arr[j-1];
    }
    arr[j] = key;
  }

  // 結果の出力
  for (i = 0; i < n; i++)
    cout << arr[i] << endl;

  return 0;
}