【アルゴリズム】挿入ソート(Insertion Sort)

ソートとは？

ソートとは、あるデータを小さい順か大きい順に従って並び替えることです。

挿入ソート(Insertion Sort)

挿入ソートとは、配列をインデックスの順番で見ていき、今取り出した値を整列済み(ソート済み)の配列に挿入していくソートです。

例えば、トランプで大富豪を行うときに、最初にトランプを左から右に見ていきながら、数が左が一番小さく、右が一番大きくなるような並び順に並び替えると自分がどのようなカードを持っているのか把握しやすいですよね？

これと同じことを行っているのが挿入ソートです。

挿入ソートのシンタックス

挿入ソートは、あるランダムに値が格納されている”未整列の配列"から値を1つ取り出し、"整列ずみの配列"にその値を加えていく作業を行います。

シンタックスは以下のようになります。

insertation_sort.js

let array = [1,3,2,5,4];

function insert_sort (array) {
  for (let i = 1; i < array.length; i++;) {
    let j;
    let tmp = array[i];
    
    for (j = i - 1; j>=0; j--;) {
      if(tmp > array[j]) {
        break;
      } else {
      　　array[j + 1] = array[j]
      }
    } // for文2つ目
    array[j + i] = tmp;
    
  } // 1つ目のfor文
}

以下のようにもかけます。

another_example.js

function insert_sort2 (array, N) { // Nはarrayの要素数
  for (let i = 1; i < array.length; i++) {
    v = array[i];
    j = i - 1;
    while (j >=0 && array[j] > v) {
      array[j + 1] = array[j];
      j--;
    }
    array[j + 1] = v;
  } // 1つ目のfor文

}