Insertion Sort (with JavaScript)

# Insertion Sort

각 iteration마다 하나의 값을 정렬된 값들 사이 적절한 위치에 삽입하는 방식으로 동작하는 정렬이다.

Insertion sort의 특징은 다음과 같다.

• 코드량이 짧다 (C/C++의 경우 세 줄로도 가능하다고 한다.)
• 최악의 경우 시간 복잡도가 O(n2)이기에 주로 작은 데이터 처리 시 활용된다.
• 일반적인 경우 selection sort, bubble sort 등 다른 quadratic algorithm보다 빠르다.
• Input이 어느 정도 정렬된 경우 효율적이다 (Adaptive sort)
• 두 인덱스에서 같은 값을 가지는 경우 인덱스 순서대로 정렬된다. (Stable)
• Input 크기에 비례하는 추가 메모리를 필요로 하지 않는다. (In-place)
• Input이 일부분씩 들어오더라도 처리할 수 있다. (Online)

 

# Process

• Selection sort와 마찬가지로 sorted / unsorted 로 나누어 진행된다.
• 정렬 시작 시 sorted는 비어있으며, unsorted는 input 전체이다.
• unsorted의 가장 왼 쪽 element를 sorted의 가장 오른쪽 element부터 순차적으로 비교하여 적절한 위치에 삽입한다.
• 해당 작업을 unsorted sublist가 비게 될 때까지 반복한다.

 

# JavaScript로 구현

function insertionSort(array) {
  let currentValue, i, j;
  for (i = 1; i < array.length; i += 1) {
    currentValue = array[i];
    for (j = i - 1; j >= 0; j -= 1) {
      if (array[j] <= currentValue) break;
      array[j + 1] = array[j]; // shift values
    }
    array[j + 1] = currentValue;
  }
  return array;
}

sorted에서 값을 하나씩 오른쪽으로 이동시키는 것을 왼쪽 값을 오른쪽 위치에 넣는 것으로 구현하였다. (shift values라고 표시된 부분)