6장. 긍정적인 시나리오 최적화

6.1 삽입 정렬

삽입 정렬(Insertion Sort)이란?
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,
자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

삽입 정렬은 아래 단계에 따라 실행된다.

1. 첫 번째 패스스루에서 임시로 인덱스 1(2번째 셀)의 값을 삭제하고, 이 값을 임시 변수에 저장한다.
   인덱스 1의 값이 없으므로 공백이 생긴다. 이후 각 패스스루마다 다음 인덱스의 값을 삭제한다.

   데이터	8		2	3
   인덱스	0	1	2	3
   		👆

   임시 변수(index) : 4(1)

2. 공백 왼쪽에 있는 각 값을 가져와 임시 변수와 비교하여 시프트를 시작한다.
   공백 왼쪽에 있는 값이 임시 변수에 있는 값보다 크면 오른쪽으로 시프트한다.
   8이 임시 변수인 4보다 크므로 오른쪽으로 이동하고, 자연스레 공백이 왼쪽으로 이동한다.

   데이터		8	2	3
   인덱스	0	1	2	3
   	👆

   임시 변수(index) : 4(1)

3. 임시 변수에 있는 값을 공백에 삽입한다.

   데이터	4	8	2	3
   인덱스	0	1	2	3

4. 1~3단계가 하나의 패스스루이며,
   배열의 마지막 인덱스에서 패스스루를 시작할 때까지 패스스루 과정을 반복한다.
   이 때가 되면 배열이 정렬된다.

6.2 삽입 정렬 실제로 해보기

데이터	4	2	7	1	3
인덱스	0	1	2	3	4

첫 번째 패스스루

1. 인덱스 1의 값을 확인하며 첫 번째 패스스루를 시작한다.
   해당 값2를 삭제하고 임시 변수에 저장한다. 인덱스 1의 자리가 공백이 된다.

   데이터	4		7	1	3
   인덱스	0	1	2	3	4
   		👆

   임시 변수(index) : 2(1)

2. 공백 왼쪽의 값을 확인하여 임시 변수와 비교한다.

   데이터	4		7	1	3
   인덱스	0	1	2	3	4
   	👆

   임시 변수(index) : 2(1)

3. 4는 2보다 크므로 오른쪽으로 시프트한다. (이 때 공백이 왼쪽으로 이동한다.)
   공백이 배열의 왼쪽 끝에 있으므로 더이상 왼쪽으로 시프트 할 수 없다.

   데이터		4	7	1	3
   인덱스	0	1	2	3	4

   임시 변수(index) : 2(1)

4. 임시 변수 값인 2를 공백에 삽입하여 첫 번째 패스스루를 종료한다.

   데이터	2	4	7	1	3
   인덱스	0	1	2	3	4

두 번째 패스스루

5. 인덱스 2의 값을 확인하며 첫 번째 패스스루를 시작한다.
   해당 값을 삭제하고 임시 변수에 저장한다. 인덱스 2의 자리가 공백이 된다.

   데이터	2	4		1	3
   인덱스	0	1	2	3	4
   			👆

   임시 변수(index) : 7(2)

6. 공백 왼쪽의 값을 확인하여 임시 변수와 비교한다.

   데이터	2	4		1	3
   인덱스	0	1	2	3	4
   		👆

   임시 변수(index) : 7(2)

7. 4는 7보다 작으므로 시프트하지 않으며,
   임시 변수 값인 7를 공백에 삽입하여 두 번째 패스스루를 종료한다.

   데이터	2	4	7	1	3
   인덱스	0	1	2	3	4

세 번째 패스스루

8. 인덱스 3의 값을 확인하며 세 번째 패스스루를 시작한다.
   해당 값을 삭제하고 임시 변수에 저장한다. 인덱스 3의 자리가 공백이 된다.

   데이터	2	4	7		3
   인덱스	0	1	2	3	4
   				👆

   임시 변수(index) : 1(3)

9. 공백 왼쪽의 값을 확인하여 임시 변수와 비교한다.

   데이터	2	4	7		3
   인덱스	0	1	2	3	4
   			👆

   임시 변수(index) : 1(3)

10. 7은 1보다 크므로 오른쪽으로 시프트한다.

    데이터	2	4		7	3
    인덱스	0	1	2	3	4
    				👆

11. 다시 공백 왼쪽의 값을 확인하여 임시 변수와 비교한다.

    데이터	2	4		7	3
    인덱스	0	1	2	3	4
    		👆

    임시 변수(index) : 1(3)

12. 4는 1보다 크므로 오른쪽으로 시프트한다.

    데이터	2		4	7	3
    인덱스	0	1	2	3	4
    			👆

    임시 변수(index) : 1(3)

13. 다시 공백 왼쪽의 값을 확인하여 임시 변수와 비교한다.

    데이터	2		4	7	3
    인덱스	0	1	2	3	4
    	👆

    임시 변수(index) : 1(3)

14. 2는 1보다 크므로 오른쪽으로 시프트한다.

    데이터		2	4	7	3
    인덱스	0	1	2	3	4
    		👆

    임시 변수(index) : 1(3)

15. 공백이 배열의 왼쪽 끝에 있으므로 더이상 시프트할 수 없다.
    임시 변수 값인 1를 공백에 삽입하여 세 번째 패스스루를 종료한다.

    데이터	1	2	4	7	3
    인덱스	0	1	2	3	4

네 번째 패스스루

16. 인덱스 4의 값을 확인하며 네 번째 패스스루를 시작한다.
    해당 값을 삭제하고 임시 변수에 저장한다. 인덱스 4의 자리가 공백이 된다.

    데이터	1	2	4	7
    인덱스	0	1	2	3	4
    					👆

    임시 변수(index) : 3(4)

17. 공백 왼쪽의 값을 확인하여 임시 변수와 비교한다.

    데이터	1	2	4	7
    인덱스	0	1	2	3	4
    				👆

    임시 변수(index) : 3(4)

18. 7은 3보다 크므로 오른쪽으로 시프트한다.

    데이터	1	2	4		7
    인덱스	0	1	2	3	4
    					👆

    임시 변수(index) : 3(4)

19. 다시 공백 왼쪽의 값을 확인하여 임시 변수와 비교한다.

    데이터	1	2	4		7
    인덱스	0	1	2	3	4
    			👆

    임시 변수(index) : 3(4)

20. 4는 3보다 크므로 오른쪽으로 시프트한다.

    데이터	1	2		4	7
    인덱스	0	1	2	3	4
    				👆

    임시 변수(index) : 3(4)

21. 다시 공백 왼쪽의 값을 확인하여 임시 변수와 비교한다.

    데이터	1	2		4	7
    인덱스	0	1	2	3	4
    		👆

    임시 변수(index) : 3(4)

22. 2는 3보다 작으므로 시프트하지 않으며,
    임시 변수 값인 3를 공백에 삽입하여 네 번째 패스스루를 종료한다. (배열 정렬 완료)

    데이터	1	2	3	4	7
    인덱스	0	1	2	3	4

코드로 구현한다면

기본 코드

function insertSort(array) {
	for (let i = 1; i < array.length; i++) {
    	let temp = array[i];
      	let position = i - 1;
      
      	while (position >= 0) {
        	if (array[position] > temp) {
            	array[position + 1] = array[position];
              	popsition -= 1;
            } else break;
        }
      
      	array[position + 1] = temp;
    }
  
  	return array;
}

해설

function insertSort(array) {
  	// 인덱스 1부터 시작해 전체 배열을 순회한다.
	for (let i = 1; i < array.length; i++) {
      	// 각 패스스루마다 해당 인덱스의 값을 삭제하고, 임시 변수 temp에 저장한다. (= 공백)
      	// position 변수는 공백 왼쪽의 값이며 temp와 비교 대상이 된다.
      	// 패스스루를 통과하면서 position은 왼쪽으로 움직이며(-1) 각 값을 temp와 비교한다.
    	let temp = array[i];
      	let position = i - 1;
      
      	// position이 0보다 같거나 큰 동안 반복문을 실행한다.
      	while (position >= 0) {
          	// 공백 왼쪽의 값인 position이 임시 변수 temp보다 크면 오른쪽으로 시프트한다.
          	// 이어서 다음 왼쪽 값을 비교할 수 있도록 position을 -1 만큼 감소시킨다.
        	if (array[position] > temp) {
            	array[position + 1] = array[position];
              	popsition -= 1;
            // 만약 position값이 temp보다 같거나 작으면 공백을 삽입할 단계이므로 패스스루를 끝낸다.
            } else break;
        }
      
      	// 공백에 임시 값은 temp를 삽입한다.
      	array[position + 1] = temp;
    }
  
  	// 정렬된 배열을 반환한다.
  	return array;
}

6.3 삽입 정렬의 효율성

삽입 정렬에 포함된 단계를 삭제, 비교, 시프트, 삽입 네 종류로
삽입 정렬의 효율성을 알기 위해서는 각 단계별 총합을 계산해야 한다.

비교

비교는 공백 왼쪽에 있는 값과 임시 값(temp)을 비교할 때 일어난다.

배열이 역순으로 정렬되어 있는 경우, 즉 최악의 시나리오에서는 각 패스스루마다 임시 값 왼쪽에 있는 모든 수를 임시 값과 비교해야 한다. 왜냐하면 왼쪽에 있는 값들이 모두 임시 값보다 크기 때문이다. 따라서 각 패스스루는 공백이 배열의 왼쪽 끝에 위치해야만 끝이 난다.

첫 번째 패스스루에서는 인덱스 1의 값이 임시 값이므로, 임시 값 왼쪽에 있는 값이 하나 뿐이다.
고로 최대 1번의 비교가 일어난다.

이와 같이 두 번째 패스스루에서는 최대 2번,
마지막 패스스루에서는 원소가 $N$개일 때 최대 $N - 1$번의 비교가 일어난다.

🧐 그렇다면 총 비교 횟수는 어떻게 계산할 수 있나요?

삽입 정렬의 총 비교 횟수는 $1 + 2 + 3 + ... + (N - 1)번$으로 표현할 수 있다.

🤓 원소의 갯수로 예를 들면?

만약 원소가 5개인 배열이라면, 최대 $1 + 2 + 3 + 4 = 10번$의 비교가 일어난다.
원소가 10개라면, $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45번$의 비교가 일어난다.

이러한 패턴은 결국 원소가 $N$개인 배열일 때, 약 $N^2 / 2번$의 비교가 일어난다고 볼 수 있다.

시프트

시프트는 값을 한 셀 오른쪽으로 옮길 때마다 일어난다.

만약 배열이 역순으로 정렬되어 있다면 비교가 일어날 때마다 시프트가 일어나므로 시프트 횟수는 비교 횟수와 같다.

🤯 그럼 최악의 시나리오일 때, 비교와 시프트 횟수를 합치면...?

• 비교 : $N^2 / 2번$
• 시프트 : $N^2 / 2번$
• 비교 + 시프트 : $N^2번$

삭제와 삽입

삽입 정렬에서 배열의 데이터(= 임시 값)을 삭제하고, 다시 삽입하는 작업은 각 패스스루당 1번 일어난다.

원소가 $N$개일 때, 패스스루는 $N - 1$번 일어나므로 결국 삭제와 삽입도 각각 $N - 1$번 일어나게 된다.

총합

• 비교 : $N^2 / 2번$
• 시프트 : $N^2 / 2번$
• 삭제 : $N - 1번$
• 삽입 : $N - 1번$

따라서 총합은 $N^2 + 2N - 2단계$가 소요된다.

그러나 빅 오에서는 지수를 제외한 상수는 무시하기 때문에 $O(N^2 + N)$으로 단순화 할 수 있다.

하나 더 중요한 것은 빅 오에는 또 다른 규칙이 있다는 점이다.

다양한 차수가 한데 섞여 있을 때, 빅 오 표기법은 가장 높은 차수의 $N$만 고려한다.

만약 $N^4 + N^3 + N^2 + N단계$가 소요되는 알고리즘이 있다고 가정했을 때,
빅 오에서는 $N^4$만 중요하게 여기며 $O(N^4)$이라고 부른다.

🫠 왜죠?

$N$	$N^2$	$N^3$	$N^4$
2	4	8	16
5	25	125	625
10	100	1,000	10,000
100	10,000	1,000,000	100,000,000

위 테이블로 살펴보면, $N$이 증가할수록 다른 차수보다 가장 높은 차수인 $N^4$의 비중이 훨씬 커져 다른 데이터들이 미미해보이기 때문이다. 테이블의 세 번째 줄에 있는 데이터를 모두 합해보면 $11,110$이다. 이 수를 내림처리하면 $10,000$이 되어 $N^4$의 결과와 가장 가깝고 다른 낮은 차수를 무시한 것과 같다.

삽입 정렬에도 동일한 개념을 적용할 수 있다.

$N^2 + N$으로 이미 한 차례 단순화 했지만, 낮은 차수를 버림으로써 $O(N^2)$으로 표현식을 더욱 단순화하여 사용한다.

버블 정렬 vs 선택 정렬 vs 삽입 정렬

5장에서 버블 정렬과 선택 정렬은 둘 다 $O(N^2)$의 효율성을 가졌다. 하지만 버블 정렬은 $N^2$단계인데 반해 선택 정렬은 $N^2 / 2$단계로 버블 정렬보다 빠르다.

삽입 정렬도 $N^2$단계가 걸리므로 버블 정렬만큼 느리다고 할 수 있다. 그리고 세 가지 정렬 방법 중 선택 정렬이 다른 정렬에 비해 2배 빠르므로 가장 나은 방법이라고 생각할 수 있다. 과연 정말 그럴까?

6.4 평균적인 경우

최악의 시나리오에서는 선택 정렬이 삽입 정렬보다 빠른 것이 사실이다.

하지만 평균적인 시나리오도 분명 고려해야 한다.
왜냐하면 가장 자주 일어나는 경우가 평균 시나리오이기 때문이다.

위와 같이 최악의 시나리오와 최선의 시나리오는 상대적으로 드물게 발생하고 실제로는 대부분 평균 시나리오가 일어난다. 만약 임의로 정렬된 배열을 생각해보면, 배열 내 데이터들이 완벽히 오름차순이나 내림차순으로 정렬된 경우보다 여기저기 흩어져 있는 경우가 더 많이 일어날 법하다는 것을 알 수 있다.

🤓 모든 시나리오 관점에서 삽입 정렬을 검토해보면?

최악의 시나리오 (역순 정렬)

역순으로 정렬된 배열에서 삽입 정렬은 각 패스스루마다 모든 값을 비교하고 시프트한다. (총 $N^2$번의 비교와 시프트 발생)

최선의 시나리오 (오름차순 정렬)

이미 오름차순으로 정렬된 배열에서 삽입 정렬은 모든 값이 이미 올바른 위치에 있으므로 각 패스스루당 한 번의 비교만 발생하며 시프트는 일어나지 않는다.

평균적인 시나리오 (임의 정렬)

임의로 정렬된 배열에서는 삽입 정렬을 할 때 모든 데이터 혹은 일부 데이터를 비교하고 시프트하거나, 혹은 비교나 시프트가 일어나지 않는 패스스루가 발생할 수도 있다.

6.2 삽입 정렬 실제로 해보기에서 첫 번째와 세 번째 패스스루에서는 비교와 시프트가 일어났지만, 두 번째 패스스루에서는 한 번의 비교만 수행할 뿐 시프트는 일어나지 않는다.

그 이유는 각 패스스루마다 공백 왼쪽 값을 임시 값과 비교하는 반면,
공백 왼쪽의 값이 임시 값보다 작을 경우 패스스루가 일찍 종료되기 때문이다.

따라서 결론을 지어보면, 삽입 정렬은 시나리오에 따라 성능이 크게 좌우됨을 알 수 있다.

• 최악의 시나리오에서 모든 데이터를 비교하고, 시프트 한다. (= $O(N^2)$)
• 최선의 시나리오에서 패스스루당 한 번의 비교만 수행하고 시프트는 하지 않는다.
• 평균 시나리오에서 대체적으로 데이터의 반을 비교하고, 시프트 한다. (= $O(N^2 / 2)$)

❗️ 하지만 빅 오의 관점에서는 최악의 시나리오를 고려하므로 모두 $O(N^2)$이다.

	최선	평균	최악
선택 정렬	$N^2 / 2$	$N^2 / 2$	$N^2 / 2$
삽입 정렬	$N$	$N^2 / 2$	$N^2$

위 테이블은 선택 정렬과 삽입 정렬을 비교한 것이다.
과연 어떤 것이 더 나을까? 정답은 경우에 따라 다르다는 것이다.

• '임의로 정렬된' 배열 같이 평균적인 경우라면, 두 정렬이 유사하게 수행된다.
• '거의 정렬된' 배열을 다룬다는 가정이 있다면, 삽입 정렬이 더 낫다.
• '역으로 정렬된' 배열을 다룬다는 가정이 있다면, 선택 정렬이 더 낫다.

6.5 실제 예제

다음은 두 배열의 교집합을 구하는 알고리즘이다.

• 변경 전

function getIntersection1(array1, array2) {
	let intersection = [];
  
  	for (let i = 0; i < array1.length; i++) {
    	for (let j = 0; j < array2.length; j++) {
        	if (array1[i] === array2[j]) {
            	intersection.push(array1[i]);
            }
        }
    }
  
  	return intersection;
}

getIntersection1 함수는 중첩 루프를 실행하며 비교와 삽입을 수행한다.

만약 매개변수로 받은 두 배열의 길이가 같고, 원소가 $N$개라면 총 $N^2$번의 비교를 수행하므로 효율성은 $O(N^2)$이다. 더불어 같은 기준에서 삽입은 최대 $N$번 수행한다. 하지만 비교에 비해 차수가 낮으므로 빅 오에서는 무시하게 되며 효율성은 여전히 $O(N^2)$이다.

만약 두 배열의 크기가 다르다면 $O(N * M)$으로 표기할 수 있다.

이 알고리즘의 효율성을 향상시키면 아래와 같이 수정이 가능하다.

• 변경 후

function getIntersection2(array1, array2) {
	let intersection = [];
  
  	for (let i = 0; i < array1.length; i++) {
    	for (let j = 0; j < array2.length; j++) {
        	if (array1[i] === array2[j]) {
            	intersection.push(array1[i]);
              	break;
            }
        }
    }
  
  	return intersection;
}

만약 두 배열에서 어떤 공통 값을 찾았다면 그 이후 단계는 진행할 필요가 없다.
고로 getIntersection2 함수에서는 break 문을 추가하여 불필요한 단계를 줄여 효율성이 높일 수 있다.

만약 두 배열에서 공통 값을 하나도 포함하지 않는 최악의 시나리오라면, $N^2$번의 비교를 수행해야 하지만, 두 배열이 동일한 최선의 시나리오에서는 $N$번의 비교만 수행하면 된다. 그리고 두 배열이 서로 다르지만 일부 값을 공통으로 가지고 있는 평균적인 시나리오에서는 $N$ ~ $N^2$ 사이의 성능을 가지게 된다.

실습

1. $3N^2 + 2N + 1$단계가 걸리는 알고리즘의 효율성은?

정답 : $O(N^2)$

2. $N + logN$단계가 걸리는 알고리즘의 효율성은?

정답 : $O(N)$

3. 다음 함수에서 최선, 평균, 최악의 시나리오는 무엇인가?
   그리고 최악의 시나리오를 빅 오 표기법으로 나타낸다면?

function isTwoSum(array) {
	 for (let i = 0; i < array.length; i++) {
     	for (let j = 0; j < array.length; j++) {
        	if (i !== j && array[i] + array[j] === 10) {
            	return true;
            }
        }
     }
  
  	return false;
}

• 최선 : 처음 두 숫자를 합해서 10이 나오는 경우
• 평균 : 배열의 중간 부근 값 두 숫자를 합해서 10이 나오는 경우
• 최악 : 배열의 마지막 두 숫자를 합해서 10이 나오는 경우
  
  위 알고리즘은 중첩 루프를 순회하므로 최악의 시나리오일 경우 $O(N^2)$의 효율성을 가진다.

4. 다음 함수의 시간 복잡도를 빅 오 표기법으로 나타내면?
   그리고 코드를 수정하여 평균 시나리오에서 효율성을 향상시키면?

function isContainsX(string) {
	let flag = false;
  
  	for (let i = 0; i < string.length; i++) {
    	if (string[i] === "X") flag = true;
    }
  
  	return flag;
}

문자열의 길이가 $N$일 때 위 알고리즘의 효율성은 $O(N)$이다.

그러나 X를 찾아도 문자열을 모두 순회하기 때문에,
아래와 같이 X를 찾을 경우 순회를 종료하고 true를 반환하며 효율성을 높일 수 있다.

function isContainsX(string) {
  	for (let i = 0; i < string.length; i++) {
    	if (string[i] === "X") return true;
    }
  	return false;
}

요약

• 삽입 정렬이란 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
• 삽입 정렬에 포함된 단계를 '삭제, 비교, 시프트, 삽입' 네 종류로, 삽입 정렬의 효율성을 알기 위해서는 각 단계별 총합을 계산해야 한다.