[알고리즘] 정렬 - 삽입 정렬(Insertion Sort) (자바스크립트/node.js/javascript/알고리즘)

삽입 정렬

삽입 정렬이란?

배열을 순차적으로 검색하면서 정렬되지 않은 항목들을 배열의 왼쪽의 정렬된 부분으로 이동시킨다.

 

동작 과정

예를 들어 [3, 7, 2, 5, 1, 4]의 배열을 오름차순으로 정리한다고 하면

• 첫번째 숫자는 놔두고 두번째 자리 숫자부터 뽑아서 그 숫자가 첫 숫자보다 크면 첫 숫자 오른쪽에, 작으면 왼쪽에 넣는다.
• 세번째 자리 숫자를 뽑아서 앞의 두 숫자와 크기를 비교해서 알맞은 자리에 넣는다.
• 이렇게 끝까지 계속 한다.

시간 복잡도

• Worst Case: O(n^2): 정렬이 하나도 안되어있는 경우
• Best Case: O(n): 이미 정렬이 되어있는 경우

공간 복잡도

• O(1) 

장점

메모리가 절약된다. (배열을 새로 만들 필요 없이 주어진 배열 안에서 정렬시키면 되기 때문, in place)

 

단점

자료의 개수가 많아지면 성능이 떨어진다. (최악의 경우 O(n^2) 이기 때문)

---

코드

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

첫번째 원소는 그대로 두기 때문에 두번째 원소부터 반복문을 돈다. temp라는 임시 변수에 값을 저장해놓고, 자신의 왼쪽부터 비교하여 현재 원소보다 왼쪽 원소가 더 크다면 반복문을 돌며 swap 작업을 한다. 그리고 계속해서 왼쪽 원소와 또 비교한다. 이렇게 해서 왼쪽 원소의 인덱스가 0이 될때까지 비교를 하면 된다.

 

참고한 사이트

www.zerocho.com/category/Algorithm/post/57e39fca76a7850015e6944a

im-developer.tistory.com/133

[JS/Sorting] 버블 정렬, 삽입 정렬, 선택 정렬 자바스크립트로 구현하기 (Bubble Sort, Insertion Sort, Select