挿入ソートをJavaScriptで実装してみる

Wikipediaの挿入ソートのC言語サンプルをそのままちょくやくしただけ。

キモはwhile部分。挿入したい要素以外の要素を後ろにずらし、x[j - 1] > tmpの時点で終了して要素をそこにぶっこむ。

function isort(x) {
  for (var i = 1; i < x.length; i++) {
    var tmp = x[i];
    if (x[i - 1] > tmp) {
      var j = i;

      while (j > 0 && x[j - 1] > tmp) {
        x[j] = x[j - 1];
        // console.log("tmp: ", tmp, "x[j]: ", j, x[j]);
        j--;
      }
      x[j] = tmp;
    }
  }
  return x;
}
console.log(isort([4,3,5,2,1]));