[Javascript] Insertion Sort (삽입 정렬) 구현 코드

Insertion Sort (삽입 정렬)

삽입 정렬은 현재값을 이전 요소들과 비교해서 자신의 자리에 "끼워 넣는" 방식이다.
선택 정렬이 현재값과 이후 요소들을 비교한다면 삽입 정렬은 이전 요소들과 비교한다는 차이가 있고,
선택 정렬이 이후 요소들 중 최소값을 찾아서 스왑한다면, 삽입 정렬은 이전 요소들을 타고 내려가는 느낌? 어떤 점에선 버블 정렬이랑 좀 비슷한 것 같다. 다만 이전 요소들은 이미 정렬이 되었기 때문에 자신의 자리를 찾아간다는 게 또 차이지만.

수도코드

1. 이중 반복문을 선언한다.
  2. 첫 번째 반복문은 현재값 i를 규정한다.
  	변수에 현재값을 저장한다. (인덱스가 한 칸씩 밀려나기 때문에 미리 저장)
        인덱스를 저장할 변수를 선언한다. (나중에 해당 인덱스로 현재값을 이동시킨다)
  3. 두 번째 반복문은 이전값 j를 규정한다. (j는 역순으로 내려간다)
  	i번째 요소와 j번째 요소를 비교한다
          i가 작다면 j의 인덱스는 한 칸씩 밀려나고 인덱스 변수에는 j를 저장한다.
          i가 크다면 break
  4. 두 번째 반복문이 끝난 후 i를 해당하는 위치에 옮긴다.
5. 정렬된 배열을 리턴한다.

코드구현

const arr = [1, 9, 8, 16, 5, 2, 7, 3];

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let cur = arr[i];
    let index = i;
    for (let j = i - 1; j >= 0; j--) {
      if (cur < arr[j]) {
        arr[j + 1] = arr[j];
        index = j;
      } else {			
        break;
      }
    }
    arr[index] = cur;
  }
  return arr;
}

const result = insertionSort(arr);
console.log(result); // [1, 2, 3, 5, 7, 8, 9, 16];

인덱스 때문에 엄청 헤맴..
두번째 반복문의 조건문을 반복문 조건과 통합할 수도 있다.

const arr = [1, 9, 8, 16, 5, 2, 7, 3];

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

const result = insertionSort(arr);
console.log(result); // [1, 2, 3, 5, 7, 8, 9, 16];