挿入ソート

挿入ソートとは

挿入ソートは、データ列の中で、ソートされた部分とまだソートされていない部分に分けて、 ソートされているデータ列に新たな未ソート部分の値を挿入していくソート方法です。

では、 挿入ソートを例題をあげて解説してみます。

挿入ソートの例題

まず次のようなデータがあるとします。

20 4 18 5 1

このデータを挿入ソートを使って昇順に並べ替えてみたいと思います、

赤数字がソート対象となり、青数字が未ソート部分で、緑数字ソートが終わった部分とします。

まず、1番目と2番目の要素に着目してソートを行います。

20 4 18 5 1

4 20 18 5 1

まず、最初の20と4が対象となり、20 > 4なので、左右を入れ替えます。

次に3番目の要素である18に着目してソートを行います。

4 20 18 5 1

4 20 18 5 1

20 > 18 なので、18の位置を決定するために、さらに左の要素を見ることになります。

次に4,18に着目します。

4 20 18 5 1

4 18 20 5 1

4 < 18なので、先程入れ替え対象となった、2番目の要素20の位置に18を挿入して、 次の要素を見ていきます。

次は4番目の要素である5に着目してソートを行います。

4 18 20 5 1

4 18 20 5 1

4 18 20 5 1

4 5 18 20 1

1.
まず、20 > 5なので3番目の要素が挿入位置となります。

2.
18 > 5なので、2番目の要素が挿入位置となります。

3.
4 < 5なので、2番目の位置が挿入位置となりました。

4.
2番目の位置に18を挿入します。

次は、最後の要素1に着目して上記の操作を行います。

こうした手順でソートすることを挿入ソートといいます。

では、最後にc++でソースを載せます。

// 挿入ソート
void InsertSort(int x[],int n){
 int temp;
 for (int i = 1; i < n; i++) {
  for (int j = i-1; j >= 0; --j) {
   if (x[j] > x[j+1]) {
    temp = x[j];
    x[j] = x[j+1];
    x[j+1] = temp;
   } else break;
  }
 }
}