Insertion Sort(삽입 정렬)

삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 정렬방법이다.

앞서 알아보았던 선택 정렬(Selection)과 버블 정렬(Bubble)은 반복을 무조건 수행해야 했다.

이번에 알아볼 삽입 정렬(Insertion)은 필요한 경우에만 위치를 변경한다.

삽입 정렬의 경우 특수한 경우에서는 굉장히 빠르게 작동한다. 따라서 시간 복잡도 O(n^2)중에서는 가장 빠르게 작동한다.

1. Insertion Sort(삽입 정렬) 문제

예제를 통해서 삽입 정렬을 한 번 알아보자

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하라.

1 10 5 8 7 6 4 3 2 9

2. Insertion Sort(삽입 정렬) 풀이

앞선 정렬들과 마찬가지 문제를 삽입 정렬로 풀어보자

1 10 5 8 7 6 4 3 2 9

삽입 정렬은 한 요소당 앞과 뒤의 공간이 있다고 보는데서 출발한다.

_ 1 _ 10 _ 5 _ 8 _ 7 _ 6 _ 4 _ 3 _ 2 _ 9 _

위와 같이 보았을 때 가장 앞의 요소와 두번째 요소를 놓고

1 의 앞과 뒤중에 10은 어느곳에 들어가야 하는지 생각하고 넣어보자

당연히 1의 오른쪽에 위치한다.

다음 단계를 살펴보자

1 10 의 세 "" 중에 어느 부분에 5가 들어가야하는가

가운데에 들어가야한다.

이런식으로 계속 전개하여

_ 1 _ 5 _ 10 _ 8 7 6 4 3 2 9

_ 1 _ 5 _ 8 _ 10 _ 7 6 4 3 2 9

_ 1 _ 5 _ 7 _ 8 _ 10 _ 6 4 3 2 9

_ 1 _ 5 _ 6 _ 7 _ 8 _ 10 _ 4 3 2 9

_ 1 _ 4 _ 5 _ 6 _ 7 _ 8 _ 10 _ 3 2 9

_ 1 _ 3 _ 4 _ 5 _ 6 _ 7 _ 8 _ 10 _ 2 9

_ 1 _ 2 _ 3 _ 4 _ 5 _ 6 _ 7 _ 8 _ 10 _ 9

_ 1 _ 2 _ 3 _ 4 _ 5 _ 6 _ 7 _ 8 _ 9 _ 10 _

최종적으로는 1 2 3 4 5 6 7 8 9 10 으로 정렬이 완료된다.

삽입 정렬이 앞선 선택 정렬과 버블 정렬보다 효율적인 이유를 생각해보자면

_ 1 _ 5 _ 7 _ 8 _ 10 _ 6 4 3 2 9 의 경우에 6이 들어갈 위치를 찾을 때

이미 6앞의 숫자들은 정렬이 완료된 상태이고 6은 그저 앞에 있는 숫자가 6보다 작은지만 판별하면된다.

10, 8, 7 총 3번의 비교만 하면된다.

그렇기 때문에 비교적 횟수가 적은 경우가 생긴다.

물론 복잡도 O(n^2)을 가지기 때문에 추후에 배울 정렬보다는 효율이 떨어진다.

// 다음의 배열을 오름차순으로 정렬하시오
const arr = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9];

// 변수들을 바꿀때 사용하는 일시적 변수 temp
let temp;

//
let j;

for (let i = 0; i < arr.length; i++) {
	j = i;
	// 왼쪽 요소와 오른쪽 요소를 비교하여
	// 왼쪽의 요소가 더 큰 경우에 코드를 실행한다
	while (arr[j] > arr[j + 1]) {
		// 위치를 바꾸는 연산을 하고
		temp = arr[j];
		arr[j] = arr[j + 1];
		arr[j + 1] = temp;

		// 위치가 변경되었으므로 다음 요소와 비교를 위해서 j를 1만큼 줄인다
		j--;
	}
}

console.log(arr);

3. Insertion Sort(삽입 정렬)의 효율성

삽입 정렬은 이론상 시간복잡도를 O(n^2)를 가진다.

하지만, 실제로 실행해보면 이미 정렬된 부분이 존재하므로 횟수가 다른 정렬들 보다 적다.

만약 2 3 4 5 6 7 8 9 10 1 이라는 특수한 경우가 존재하면,

이미 거의 정렬이 되어있기 때문에 연산 횟수가 다른 어떤 정렬들보다 적게 일어날 수도 있다.

버블, 선택 정렬의 경우에는 정렬이 되어있는지 알 수 없기 때문에 연산 횟수가 삽입정렬보다 많이 일어난다.

참고자료

동빈나 유튜브
https://www.youtube.com/watch?v=qQ5iLNjpxSk&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz