02.insertion-sort.md

Insertion Sort

본 내용은 뇌를 자극하는 알고리즘 (한빛미디어) 책을 공부하면서 정리한 내용입니다.

삽입 정렬은 버블 정렬과 마찬가지로 구현이 쉽다. 버블 정렬과 마찬가지로 개발자들에게 애용되는 알고리즘 이지만 성능이 썩 좋은 편은 아니다.

Description

• 정렬 대상은 왼쪽부터 선택한다. 첫 대상 범위는 2개지만, 알고리즘 횟수가 늘어날수록 1개씩 커진다.

• 정렬 대상의 가장 오른 쪽에 위치한 요소를 기준으로 잡고 그 값을 적절한 위치에 위치시켜준다.(insert)

• 기준이 되는 요소보다 큰 값들(오름차순일 경우)을 한 칸 씩 미룬다.

ex) [5] [1] [6] [4] [2] [3]

1st round: [1] -> [5] | [6] [4] [2] [3]  -> 정렬 기준은 [5]

2nd round: [1] [5] [6] | [4] [2] [3]     -> 정렬 기준은 [6]

3rd round: [1] [4] -> [5] [6] | [2] [3]  -> 정렬 기준은 [4]

4th round: [1] [2] -> [4] [5] [6] | [3]  -> 정렬 기준은 [2]

5th round: [1] [2] [3] -> [4] [5] [6]    -> 정렬 기준은 [3]

Code

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

const insertionSort = array => {
  let length = array.length;
  // subarray를 만들어서 비교한다고 생각하면 된다.

  // 첫번째 요소는 건너띄기 때문에 1부터 시작
  for (let i = 1; i < length; i++) {
    const target = array[i];

    for (let j = i - 1; j >= 0; j--) {
      if (array[j] > target) {
        // 해당 조건일 경우.
        array[j + 1] = array[j]; // 한 칸씩 미루기
        array[j] = target; // 빈 칸에 값 넣기
      }
    }
  }
  console.log(array);
};

insertionSort(array);