CS) 정렬 - 삽입 정렬과 효율성

김명성·2023년 6월 8일

버블 정렬과 선택 정렬을 알아보면서 둘다 최악의 경우로 알고리즘의 단계를 분석했지만 삽입 정렬을 배우면서 다른 시나리오를 분석하는 것에 어떤 장점이 있는지 알아보자.

삽입정렬

간단 요약
1. 기준 인덱스의 값을 가지고 기준 인덱스 왼쪽으로 순회한다
2. 비교 인덱스의 값이 기준 인덱스의 값보다 크면 1칸씩 앞으로 시프트한다.
3. 비교 인덱스의 값이 기준 인덱스의 값보다 작으면 그대로 breaking한다.(왼쪽의 인덱스가 남아 있더라도 종료)
4. 패스 스루가 종료된 인덱스에 기준 인덱스의 값을 삽입한 후 다음 패스 스루로 이동하며 큰 값이 왼쪽으로 오게끔 정렬된다.

삽입 정렬의 패스 스루

예시의 empty는 이해를 돕기 위한 것으로 실제로는 존재하는 값을 덮어씌웁니다

const arr = [5,9,4,1,3]

1단계. 인덱스 1번의 값 9를 확인하고 해당 인덱스를 임시로 삭제한 뒤 temp_value에 저장한다.

2단계. temp_value와 왼쪽 인덱스를 비교한다. 여기서는 인덱스 0번의 5와 비교한다.

3단계. temp_value보다 작은 값을 마주쳤으므로 시프트를 하지 않고 다시 공백에 삽입한다.

첫 번째 패스 스루에서는 아무 일도 일어나지 않았다.

두 번째 패스 스루를 시작한다.

1단계. 첫 번째 패스스루를 시작했던 인덱스의 다음 인덱스부터 시작한다. 여기서는 인덱스 2인 4이다. 인덱스 2를 삭제한 뒤 값 4를 temp_value에 저장한다.

2단계. temp_value와 왼쪽 인덱스를 비교한다. 여기서는 인덱스 1번인 9와 temp_value 5를 비교한다.

3단계. temp_value 5보다 인덱스1의 9가 더 크므로 오른쪽으로 시프트한다. 이제 배열은 [5,empty,9,1,3]의 형태다.

4단계. temp_value와 비교를 진행했던 왼쪽 인덱스를 비교한다. 여기서는 인덱스 0의 5와 비교한다.

5단계. temp_value 5보다 인덱스 0의 5가 더 크므로 오른쪽으로 시프트한다. 이제 배열은 [empty,5,9,1,3]의 형태다.

6단계. 공백이 배열의 왼쪽 끝에 도달하였으므로 temp_value를 공백에 삽입하고 패스 스루를 끝낸다.

두 번째 패스스루에서 temp_value보다 큰 2개의 값을 만나 오른쪽으로 두 번 시프트하였다. 이제 배열은 [4,5,9,1,3]의 형태다.

세 번째 패스 스루를 시작한다.

1단계. 두 번째 패스 스루를 시작했던 인덱스의 다음 인덱스부터 시작한다. 여기서는 인덱스 3인 1이다. 인덱스 3을 삭제한 뒤 1을 temp_value에 저장한다.

2단계. temp_value와 왼쪽 인덱스를 비교한다. 여기서는 인덱스 2번인 9와 temp_value인 1을 비교한다.

3단계. temp_value 1은 9보다 작으므로 9는 오른쪽으로 시프트한다.

4단계. temp_value와 그 다음의 왼쪽 인덱스와 비교한다. 여기서는 인덱스 1번의 5와 비교한다.

5단계. temp_value는 5보다 작으므로 5는 오른쪽으로 시프트한다.

6단계. temp_value와 그 다음의 왼쪽 인덱스와 비교한다. 여기서는 인덱스 0인 4와 비교한다.

7단계. temp_value는 4보다 작으므로 4는 오른쪽으로 시프트한다.

8단계. 공백이 배열의 왼쪽 끝에 도달하였으므로 temp_value를 공백에 삽입하고 패스스루를 끝낸다.

이제 배열은 [1,4,5,9,3]의 형태다.

네 번째 패스 스루를 시작한다.

1단계. 세 번째 패스스루를 시작했던 인덱스의 다음 인덱스부터 시작한다. 여기서는 인덱스 3인 9이다. 인덱스 3번을 삭제하고 temp_value에 9를 저장한다.

2단계. temp_value는 다시 왼쪽의 인덱스와 비교한다.

3단계 temp_value 9는 자신보다 작은 수를 마주쳤으므로 비교하지 않고 다시 공백에 저장한다.

네 번째 패스 스루에서는 아무일도 일어나지 않아 배열은 [1,4,5,9,3]이다.

다섯 번째 패스 스루를 시작한다.

1단계. 네 번째 패스 스루를 시작했던 인덱스의 다음 인덱스부터 시작한다. 여기서는 인덱스4인 3이다. 인덱스 4번을 삭제하고 temp_value에 3을 저장한다.

2단계. temp_value 다시 왼쪽의 인덱스와 비교한다.

...

삽입 정렬은 이런식으로 진행되어 배열은 [1,3,4,5,9]로 정렬되게 된다.

삽입정렬을 코드로 구현하면 다음과 같다

function insertionSort(array) {
  
  // 패스 스루 시작시 기준 인덱스(i)는 두 번째 인덱스부터 시작
  for(let i = 1; i < array.length; i++) {
    // 인덱스의 값을 임시적으로 저장한다.
    let temp_value = array[i];

    // 패스 스루 시작시 비교대상 인덱스(j)는 기준 인덱스의 바로 왼쪽 인덱스
    let j = i - 1;
    // 2개의 조건이 맞지 않을 시 while문은 실행되지 않고 루프를 빠져나온다.
    while(j >= 0 && array[j] > temp_value) {
      array[j + 1] = array[j];
      j--;
    }
    // j에 +1을 하는 이유 ?
    // 패스 스루의 마지막 단계의 j--로
    // 삽입되어야 할 인덱스보다 1이 낮기 때문에 1을 더해준다.
    array[j + 1] = temp_value;
  }
  return array;
}

삽입 정렬에 포함된 단계는 삭제, 비교, 시프트, 삽입 총 4가지이다.

삽입 정렬의 효율성을 구하려면 각 단계별 총합을 계산해야 한다.

먼저 비교는 temp_value 왼쪽에 있는 인덱스를 순회하며 비교할 때마다 일어난다.

배열이 역순으로 정렬된 최악의 시나리오라면 각 패스스루마다 temp_value 왼쪽에 있는 모든 수를 비교해야한다.
temp_value 왼쪽에 있는 값이 항상 temp_value보다 크기 때문이다.
따라서 각 패스스루는 empty가 배열의 왼쪽 끝으로 가야만 끝난다.

만약 원소가 5개인 배열이라면, 패스 스루마다 왼쪽에 있는 값들이 늘면서 10(1+2+3+4)번의 비교가 있을것이다.

비교 뿐만 아니고 시프트 과정도 비교한 횟수만큼 일어난다.

또한 각 패스 스루마다 마지막에 temp_value를 삽입하는 과정도 존재한다 .

모든 과정을 합친다면 원소 N개를 가진 배열을 삽입정렬할 때 필요한 단계는 N² + 2N - 2이다.

앞서 Big O는 상수를 무시한다는 중요한 규칙으로 이 과정은 O(N² + N)으로 단순화 할 수 있다.

하지만 Big O에는 중요한 규칙이 또 있다.