insertSort

과거의 요소들과 현재요소를 비교하면서 현재요소가 있어야 할 곳에 삽입해 나가는 정렬

pointer 를 이동하면서 과거의 요소와 현재요소를 비교하면서 자리를 바꾸어 나간다.

// 요소를 전부 확인한다.

// 현재 요소를 과거에 확인했던 요소들에 삽입해 정렬해 나간다.

const array = [5, 3, 1, 3, 4, 6, 2];

function insertSort(array) {
  for (let i = 1; i < array.length; ++i) {
    let pastPointer = i - 1;

    while (pastPointer >= 0 && array[pastPointer + 1] > array[pastPointer]) {
      const temp = array[pastPointer + 1];
      array[pastPointer + 1] = array[pastPointer];
      array[pastPointer] = temp;

      --pastPointer;
    }
  }
}

insertSort(array);

console.log(array);