Insertion Sort(挿入ソート)

寒い〜〜
クリスマスですね〜〜

最近、これを読み始めました。

https://www.amazon.co.jp/dp/4839952957/ref=cm_sw_em_r_mt_dp_U_qW0aEbEYV3WQF

メモ的に学んだことを残していきたいと思います。

前提

このアルゴリズムはソート対象の配列を、未ソート部分とソート済み部分にわけて考えます。
まだ並べ替えが行われていない段階では、先頭の要素がソート済みになります。

手順

未ソート部分がなくなるまで下の処理を繰り返します。

1. 未ソート部分先頭から要素を一つ取り出して、変数に退避させます。(ここではこの変数をtmpとします)
2. ソート済みの部分で、変数tmpより大きい要素を一つ後ろにずらします。
3. ソート済みの部分で、空いたところに変数tmpを入れます。

ソースコード

本に乗ってるやつに自分なりに変数名つけたり、コメントつけたやつです。
コードを見てもらえば、わかると思うのですが、昇順のソートです。

#include<stdio.h>

// 配列の要素を順番に出力
void trace(int array[], int size)
{
  int i;
  for (i=0; i<size; i++)
  {
    // 最初は空白を入れないのでスキップ
    if (i>0) printf(" ");
    printf("%d", array[i]);
  }
  // 改行を出力
  printf("\n");
}

// 挿入ソート関数
void insertionSort(int array[], int size) {
  int prev, current, tmp;

  for (current = 1; current < size; current++)
  {
    // 未ソート部分の先頭要素を退避
    tmp = array[current];
    // prev(ソート済み部分列からtmpを挿入する位置を探すための変数)の値
    prev = current - 1;

    /**
     * 探索変数が配列の範囲内である　かつ
     * ソート済み部分の変数が退避した変数よりも大きい限り回す
     */
    while ( prev >= 0 && array[prev] > tmp)
    {
      // 一つ後ろに退避させる
      array[prev+1] = array[prev];
      // 探索対象を遡る
      prev--;
    }

    // 空いた場所に退避した未ソート部分の先頭を挿入
    array[prev+1] = tmp;

    // ログ
    trace(array, size);
  }
}

/**
* メイン
*/
int main()
{
  int size, current, prev;
  int array[100];

  scanf("%d", &size);
  for (current=0; current<size; current++)
  {
    scanf("%d", &array[current]);
  }

  trace(array, size);
  insertionSort(array, size);

  return 0;
}

本に乗ってる図がめちゃくちゃわかりやすいので、おすすめです。

JavaScript

普段はJSをメインで書いているのでJSでも書いてみました〜
こっちには降順のパターンも載せています。

See the Pen Insertion sort by ysk (@00ysk) on CodePen.