삽입 정렬(Insertion Sort)

Insertion Sort는 Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘이다.

Insertion Sort는 '2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입' 하여 정렬하는 알고리즘이다.

최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다. 손 안의 카드를 정렬하는 방법과 유사하다.

Process

1. 정렬은 2번째 위치(index)의 값을 temp에 저장한다.
2. temp와 이전에 있는 원소들과 비교하며 삽입해나간다.
3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.

JavaScript Code

function insertionSort(arr) {

  for (let i = 1; i < arr.length; i++) {
    let currentVal = arr[i];
    let targetIdx = 1;
    
    for (let j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
        targetIdx = j;
        arr[targetIdx + 1] = arr[targetIdx]; 
    }
    if (targetIdx) {
      arr[targetIdx] = currentVal;
    }
  }
  return arr;
}

• 배열의 두번째 요소를 Pick
• 두 번째 요소를 첫번째요소와 비교하고, 필요하다면 Swap
• 다음 요소로 계속 반복, 만약 순서가 틀리다면, 정렬된 부분을 순회하면서 정확한 위치에 배치한다
• 정렬될때까지 반복한다

시간복잡도

최선의 경우는 O(n) 의 시간복잡도를 갖고, 평균과 최악의 경우 O(n^2) 의 시간복잡도를 갖게 된다.

장점

• 알고리즘이 단순하다.
• 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
  => 제자리 정렬(in-place sorting)
• '안정 정렬(Stable Sort)' 이다.
• Selection Sort나 Bubble Sort과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠르다.

단점

• 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적이다.
• Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적이다.

 

* 틀린 부분이 있다면 말씀 부탁드립니다!