[Algorithm] 삽입 정렬(Insertion Sort)

삽입 정렬?

선택 정렬과 유사한 알고리즘이지만, 더 효율적인 알고리즘이다.

삽입 정렬은 두 번째 원소부터 시작하여 목록의 정렬된 부분과 비교하여 올바른 위치에 원소를 반복적으로 삽입하여 정렬하는 알고리즘이다.

Best Case 경우 O(N)의 효율성을 갖고있어 좋은 알고리즘이다.

Visualgo Sort Algorithm GIF

알고리즘 과정

• 첫 번째 원소를 정렬된 부분으로 간주하여 시작한다.
• 두 번째 원소부터 선택하여 정렬된 부분(앞부분)과 비교하여 올바른 위치에 삽입한다.
• array가 [5, 2, 4, 6, 1, 3]라면 5는 정렬된 부분으로 간주, 2를 가져와 5와 비교한 후 2는 5보다 작기 때문에 5를 오른쪽으로 옮긴 후 그 자리에 2를 삽입한다. 정렬된 부분은 [2, 5]가 됨

GIF로 이해하는 알고리즘

알고리즘 구현

function InsertionSort(array) {
  for(let i = 1; i < array.length; i++) {
    let temp = array[i];
    let idx = i;
    while( idx > 0 && temp < array[idx - 1]){
      array[idx] = array[idx - 1];
      idx--;
    }
    array[idx] = temp;
  }
  console.log(array);
  return array;
}

InsertionSort([5, 2, 4, 6, 1, 3])