[알고리즘과 자료구조] 삽입 정렬에 대해서 알아보기

📖 '누구나 자료구조와 알고리즘' 책에 대해 공부한 내용을 담고 있습니다.

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

이전 장까지 빅 오 표기법은 최악의 시나리오 즉, 가장 좋지 않은 상황에 초점을 두어 표현하였다. 하지만 항상 최악의 시나리오만 발생하지 않는다.

6장에서는 모든 시나리오를 고려하는 방법을 배워서 적절한 알고리즘을 선택할 수 있도록 하자

6-1. 삽입 정렬

삽입 정렬이란?
2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘

삽입 정렬 알고리즘은 다음과 같은 과정을 거친다

첫 번째 패스스루

1-1. 인덱스 1의 값을 임시로 삭제하고 해당 값을 임시 변수에 저장한다. 인덱스 1에 값이 없으므로 공백이 생긴다.

8	4	2	3
	↑

	4
8		2	3
	↑

1-2. 인덱스 0과 임시 변수의 값을 비교한다. 임시 변수보다 인덱스 0의 값이 더 크므로 왼쪽 값을 오른쪽으로 이동시킨다.

	4
	8	2	3

1-3. 임시 변수의 값은 현재 공백에 삽입한다.

4	8	2	3

두 번째 패스스루

2-1. 인덱스 2의 값을 임시로 삭제하고, 임시 변수에 저장한다. 인덱스 2에 공백이 생긴다.

4	8	2	3
		↑

		2
4	8		3
		↑

2-2. 인덱스 1과 임시 변수의 값을 비교한다. 인덱스 1의 값이 크므로 8를 인덱스 2 자리로 이동시킨다.

		2
4		8	3

2-3. 인덱스 0과 임시 변수의 값을 비교한다. 인덱스 0의 값이 크므로 4를 인덱스 1 자리로 이동시킨다.

		2
	4	8	3

2-4. 임시변수와 비교한 값이 없으므로 공백에 2를 넣는다.

2	4	8	3

세 번째 패스스루

3-1. 인덱스 3의 값을 임시로 삭제하고, 임시 변수에 저장한다. 인덱스 3에 공백이 생긴다.

4	8	2	3
		↑

			3
2	4	8
			↑

3-2. 인덱스 2과 임시 변수의 값을 비교한다. 인덱스 2의 값이 크므로 8를 인덱스 3 자리로 이동시킨다.

			3
2	4		8

3-3. 인덱스 1과 임시 변수의 값을 비교한다. 인덱스 1의 값이 크므로 4를 인덱스 2 자리로 이동시킨다.

			3
2		4	8

3-4. 인덱스 0과 임시 변수의 값을 비교한다. 임시 변수의 값이 크기 때문에 2는 그 자리에 둔다.

			3
2		4	8

3-5. 임시 변수의 값 3를 공백에 넣는다.

2	3	4	8

위 과정을 거쳐 배열이 모두 정렬된다.

6-2. 삽입 정렬 실제로 해보기

Javascript로 삽입 정렬을 구현해보자

function insertion_sort(array) {
  // for 문으로 통해 인덱스 1부터 배열을 순회
  // 한 번의 루프가 하나의 패스스루를 의미
  for (let i = 1; i < array.length; i++) {
    // temp_value: 현재 인덱스 i의 값을 저장하는 임시 변수
    // position: 인덱스 i - 1 
    let temp_value = array[i];
    let position = i - 1;

    // 인덱스 i - 1 와 임시 변수 값 비교해서 값을 이동
    while (position >= 0 && array[position] > temp_value) {
      array[position + 1] = array[position];
      position = position - 1;
    }

    // 값 비교/이동을 끝낸 후 빈 공간에 임시 변수 값을 저장
    array[position + 1] = temp_value;
  }
  return array;
}

6-3. 삽입 정렬의 효율성

삽입 정렬에 포함된 단계는 삭제, 비교, 이동, 삽입, 총 4단계다. 각 단계의 합을 구해서 효율성을 알아보자

최악의 시나리오 경우

• 비교: N² / 2번
• 이동: N² / 2번
• 삭제: N - 1번
• 삽입: N - 1번

총 N² + 2N - 2번의 단계가 걸린다.

삽입 정렬은 빅 오 표기법으로 어떻게 표현할까?

빅 오 표기법은 상수를 무시한다.

빅 오 표기법은 가장 높은 차수만 표기한다.

이전 장에서 빅 오 표기법은 상수를 무시하여 단순환한다고 설명했다. 추가로 빅 오 표기법은 가장 높은 차수만 표기한다. 그 이유는 N이 증가할수록 가장 높은 차수와 다른 값의 차이가 크게 차이나기 때문에 낮은 차수를 생략한다.

삽입 정렬의 단계 수 N² + 2N - 2번에서 N²으로 단순화해서 O(N²)으로 표기한다.

6-4. 평균적인 경우

지금까지 최악의 시나리오에서의 단계 수를 알아봤다. 하지만 늘 최악의 시나리오만 있지 않기 때문에 평균 시나리오에서의 단계 수를 알아보자

최악 시니라오는 모든 수를 비교/이동해야 한다면, 평균 시나리오에서는 데이터의 반정도 비교/이동이 일어나서 약 N² / 2 정도 걸린다고 할 수 있다.
(하지만 빅 오 관점에서는 두 시나리오 모두 O(N²)이다.)

최선의 시나리오는 N-1번의 비교와 0번의 시프트가 일어나서 약 N단계 걸린다.

선택 정렬과 삽입 정렬의 비교

	최선의 시나리오	평균 시나리오	최악의 시나리오
선택 정렬	N² / 2	N² / 2	N² / 2
삽입 정렬	N	N² / 2	N²

선택정렬은 모든 경우 N² / 2단계가 걸린다. 삽입 정렬은 상황에 따라 단계수가 차이가 난다.

최선의 시나리오에서는 삽입 정렬이 낫고, 최악의 시나리오에서는 선택 정렬이 더 빠르다. 평균적인 상황에서는 선택 정렬과 삽입 정렬 모두 비슷한 효율성을 갖는다.

6-5. 실제 예제

두 배열의 교집합을 구하는 자바스크립트 앱을 만들다고 하자. 교집합은 두 배열에 모두 있는 값의 리스트다. 예를 들어 배열 [3,1,4,2]와 [2,5,3,6]이 있을 때, 교집합은 배열 [3,4]이다.

자바스크립트로 구현

이중 For 문을 사용해서 두 배열의 요소를 순회하며 교집합을 찾는다.
첫 번째 코드는 모든 원소를 다 비교하기 때문에 O(N²)이 걸린다. 중간에 교집합을 찾는다면 다음 값을 비교할 필요가 없기 때문에 불필요한 수행을 진행할 가능성이 있다.

• 첫 번째 코드

function intersection(firstArray, secondArray) {
  let result = [];
  for (let i = 0; i < firstArray.length; i++) {
    for (let j = 0; i < secondArray.length; i++) {
      if (firstArray[i] === secondArray[j]) {
        result.push(firstArray[i]);
      }
    }
  }
  return result;
}

코드에 break를 추가함으로써 이중 루프를 짧게 끝낼 수 있다. break는 이 코드에서 성능 최적화하는 부분이다. 덕분에 첫 번째 코드보다 효율적인 알고리즘을 구현할 수 있다.

• 두 번째 코드

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