알고리즘 - 삽입 정렬 (insertion sort) / 삽입 정렬 구현

삽입 정렬?

---

항목을 삽입할 공간을 만들기 위해 삽입할 항목보다 큰 항목들을 전부 오른쪽으로 밀어서 이동시키고 확보된 빈 공간에 항목을 삽입하는 정렬 알고리즘이다. 

 

📌 삽입 정렬의 동작 순서

1. 첫 패스스루에서 임시로 두 번째 셀(index = 1)의 값을 삭제하고 이 값을 저장해 둔다.
   • 인덱스 1에 값이 없이 때문에 공백이 생긴다.
   • 이후 각 패스스루마다 다음 인덱스의 값을 삭제한다.
2. 공백 왼쪽에 있는 각 값을 가져와 저장해둔 값과 비교한다.
   • 공백 왼쪽에 있는 값이 저장해둔 값보다 크면 그 값을 오른쪽으로 시프트한다.
   • 값을 오른쪽으로 시프트 해서 공백이 왼쪽으로 옮겨진다.
   • 임시로 삭제한 값보다 작은 값을 만나거나 배열의 왼쪽 끝에 도달하면 시프트 단계가 끝난다.
3. 임시로 제거한 값을 현재 공백에 삽입한다.
4. 1-3단계가 하나의 패스스루로 배열의 마지막 인덱스에서 패스스루를 시작할 때까지 패스스루를 반복한다.

 

삽입 정렬에는 삭제, 비교, 시프트, 삽입 총 네 가지 단계가 있다. 그래서 삽입 정렬의 효율성을 분석하기 위해서는 각 단계별 총합을 계산해야 한다.

 

📌  최악의 경우

삽입 정렬의 최악의 경우는 배열이 역순으로 정렬되어 있을 때이다. 원소가 N개가 있다면 1+2+3+..+N-1번의 비교, 대략 N^2/2번의 비교가 일어난다. 배열이 역순으로 정렬되어 있다면 비교가 일어날 때마다 값을 오른쪽으로 시프트해야 하기 때문에 비교 회수만큼 시프트가 일어난다. 배열로부터 저장해둔 값을 삭제하고 다시 삽입하는 작업은 패스스루당 한 번 일어난다. 패스스루는 항상 N-1이므로 결국 N-1번의 삽입이 있다. 위의 단계를 합치면 N^2+2N-2단계이다. 빅오 표기법은 상수를 무시하고 다양한 차수가 한데 섞여 있을 때 가장 높은 차수만 고려하므로 O(N^2)이다.

 

📌  최선의 경우

삽입 정렬의 최선의 경우는 배열이 이미 원하는 대로 정렬되어 있는 경우이다. 각 값이 이미 올바른 위치에 있어서 패스스루당 한 번의 비교만 하고 시프트는 일어나지 않기 때문에 원소가 N개 일 때 비교는 N-1번 일어나게 된다. 그래서 이때의 효율성은 O(N)이다.

 

📌 평균적인 경우

삽입 정렬의 평균적인 경우는 입력이 랜덤하게 정렬되어 있을 때이다. 이때는 대체적으로 데이터의 반을 비교하고 시프트할 것 이다. 비교가 N/2번 일어나고도 교환도 N/2번 일어난다. 약 N^2/2단계가 걸리지만 빅오 표기법으로 나타내게 되면 O(N^2)가 된다. 삽입 정렬이 시나리오에 따라 성능이 크게 좌우되지만 부분적으로 정렬된 배열이나 크기가 작은 배열에 적용될 때 효과적이다.

 

	최선의 경우	평균의 경우	최악의 경우
삽입 정렬	O(N)	O(N^2)	O(N^2)

 

Ex.

//list = [4,2,1,5,3]
const exchange = (list, a, b) => {
  [list[b], list[a]] = [list[a], list[b]]; // 현재 값과 작은 값 교환.
};

const less = (a, b) => a < b;

const insertionSort = (list) => {
  const { length } = list;

  for (let i = 1; i < length; i++) {
    for (let j = i; j > 0; j--) {
      if (less(list[j], list[j - 1])) {
        exchange(list, j, j - 1); // 현재 값이 교환하려는 값보다 작을 경우.
      } else {
        break; // 현재 값이 교환하려는 값보다 클 경우.
      }
    }
  }
  
  // list = [1,2,3,4,5]
};