[알고리즘] 삽입정렬

'삽입정렬'에 대해 알아보자. 알고리즘 중에는 '탐색'하고 '정렬'하는 것들이 많다. 탐색을 하기 전에는 먼저 정렬을 해야 한다. 숫자로 이루어진 배열이 있다고 하자. 숫자가 작은 순서대로 정렬 한다. '삽입정렬'은 두 번째 인덱스의 수부터 뽑아서 그 숫자가 첫 숫자보다 크면 '뒤'에, 작으면 '앞'에 위치시킨다. 이를 반복하면 오름차순으로 정렬된다.

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

insertionSort([5, 6, 1, 2, 4, 3]) // [ 1, 2, 3, 4, 5, 6 ]

for문의 중첩은 성능이 좋지 않다. 효과적인 정렬은 복잡도가 낮은데, 이 경우는 시간의 복잡도가 높기 때문이다. 그럼에도 '삽입정렬'을 사용하는 이유는 1. 작은 수에서는 간단하게 사용 가능하며 2. 이미 정렬된 배열에 새로운 요소를 집어넣어 다시 정렬할 때에는 효과적이기 때문이다.

참고자료