[알고리즘 with JS] 삽입 정렬 (insertion sort)

삽입 정렬은 처음 요소가 정렬되어 있다고 가정하고,
그다음 요소와 비교하여 알맞은 자리에 삽입한다.

 

삽입 정렬에서 중요한 것은 첫 번째 값이 정렬되어 있다고 가정하여
두 번째 요소에서 시작하는 것이다.

두 번째 요소를 앞에 있는 값과 비교하여 교환이 필요하다면 swap 한다.

function insertionSort(arr) {
  for (let i=1; i<arr.length; i++) {
    let currVal = arr[i];
    let j = i-1;
    while (j >= 0 && arr[j] > currVal) {
      arr[j+1] = arr[j];
      j--;
    }
    arr[j+1] = currVal;
  }
  return arr;
}

// while문 -> for문
function insertionSort(arr) {
  for (let i=1; i<arr.length; i++) {
    let currVal = arr[i];
    for (let j=i-1; j >= 0 && arr[j] > currVal; j--) {
      arr[j+1] = arr[j];
    }
    arr[j+1] = currVal;
  }
  return arr;
}

두 번째 요소부터 for 문을 돌며 현재 값과 전 값을 비교하고,
현재 값이 전 값보다 작다면 교환하여 정렬해 나아간다.