挿入ソートのアルゴリズム 与えられた配列をソートする際、挿入ソートを用いるとする。 与えられた配列を、ソート済みの配列(長さは1)と未ソートの配列に分割する。未ソートの配列の中から一つ選び、ソート済みの配列に挿入する。挿入された値と、隣り合う要素同士を比較し、インデックスを入れ替えながら配列を並び替えていく。 アルゴリズム実装 O(n2) TypeScript export function insertionSort(array: number[]) { for (let i = 0; i < array.length; i++) { let j = i; while (j > 0 && array[j] < array[j - 1]) { const tmp = array[j]; array[j] = array[j - 1]; array[j - 1] = tmp; j -= 1;