[알고리즘] 삽입 정렬 (Insert Sort)

삽입 정렬이란?

손 안의 카드를 정렬하는 방법과 유사한 알고리즘으로 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

삽입 정렬 알고리즘

두개의 부분집합으로 나눔 ➡ 크기에 따라 index 변경

✔ 처음 key값은 2번째 자료부터 시작한다

❗ 하나의 배열을 나누어서 부분집합을 두 개로 만드는 것이지, 집합을 두 개 만들 필요는 없다.

시간복잡도

평균 : O(N^2)
최악 : O(N^2) ➡ 역으로 정렬되어 있을 경우
최선 : O(N) ➡ 모두 정렬이 되어 있는 경우

❓ 언제 삽입 정렬을 사용하는 것이 좋을까
👉 [2, 3, 4, 5, 1] 처럼 90% 정렬이 되어있는 배열을 정렬할 때 퀵 정렬보다 빠르다

✔ 공간복잡도 : O(N)

삽입 정렬 예시

삽입 정렬 코드

const insertSort = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    let j = i;
    let tmp = 0;

    while (arr[j - 1] > arr[j]) {
      tmp = arr[j - 1];
      arr[j - 1] = arr[j];
      arr[j] = tmp;
      j--;
    }
  }
  return arr;
};