정렬 - 삽입 정렬 (Insertion Sort)

 

 

 

 

카드게임을 할 때, 카드를 손에 쥔 채로 카드를 한장씩 꺼내보면서 적절한 위치에 끼워넣어 순서대로 정렬시켜 본 경험이 한번쯤은 있을 것입니다. 정렬 알고리즘에도 이와 비슷한 것이 있는데요, 바로 삽입정렬입니다. 오늘은 다양한 정렬 중 삽입정렬에 대해 알아보도록 하겠습니다.

 

📍 삽입 정렬

삽입 정렬은 앞의 모든 원소가 정렬이 되어 있다고 가정했을 때 현재 원소를 적절한 위치에 집어넣어 정렬하는 방식입니다.

위와 같이 [2, 5, 6, 3, 4, 1] 순서의 배열에서, 앞의 2, 5, 6이 정렬되어 있는 경우 배열의 4번째 자리에 있는 3을 정렬해보도록 하겠습니다.

3을 앞의 원소와 비교했을 때, 3보다 큰 수인 6이 나왔으므로 6과 3의 자리를 바꾸어 줍니다.

그 다음 3을 앞의 원소와 비교했을 때, 3보다 큰 수인 5가 나왔으므로 5와 3의 자리를 바꾸어 줍니다.

2와 비교했을 때는 3이 더 크므로 자리를 바꾸지 않습니다. 맨 앞 까지 갔으므로 index 5의 자리 원소를 정렬해줍니다. 이 방법을 모든 배열 내 원소가 정렬될 때 까지 반복해주면 됩니다.

 

자바스크립트로 구현하면 다음과 같습니다.

for (let i = 1; i < inputArr.length; i++) {
    let j = i - 1; //i의 바로 앞 원소를 가리키기 위함
	let key = inputArr[i]; //정렬할 원소
    for (; j >= 0; j--) {
    	if (inputArr[j] > key) {
        	inputArr[j + 1] = inputArr[j];
            inputArr[j] = key;
        }
    }
}

정렬해야 할 원소(화살표로 표시된 원소)의 값을 key라고 하였을 때, 바로 앞의 원소와 비교하여 해당 값이 key보다 클 경우 자리를 바꿔주도록 구현하면 됩니다.

 

⏰ 시간복잡도

삽입 정렬의 시간복잡도는 어떻게 될까요? 최악의 경우는 모든 원소가 반대로 되어있을 경우일 것입니다.

예를 들어 [5, 4, 3, 2, 1] 이라는 배열이 있다고 생각했을 때, 삽입정렬을 자세히 표현하면 다음과 같을 것입니다.

 

key가 4인 경우 : [5, 4, 3, 2, 1] => [4, 5, 3, 2, 1]

key가 3인 경우 : [4, 5, 3, 2, 1] => [4, 3, 5, 2, 1] => [3, 4, 5, 2, 1]
key가 2인 경우 : [3, 4, 5, 2, 1] => [3, 4, 2, 5, 1] => [3, 2, 4, 5, 1] => [2, 3, 4, 5, 1]
key가 1인 경우 : [2, 3, 4, 5, 1] => [2, 3, 4, 1, 5] => [2, 3, 1, 4, 5] => [2, 1, 3, 4, 5] => [1, 2, 3, 4, 5]

 

이렇게 보았을 때, 4는 1번, 3은 2번, 2는 3번, 1은 4번을 이동하게 됩니다. 따라서 다음과 같은 식으로 표현할 수 있습니다.

1 + 2 + ... + n-2 + n-1 = n(n-1)/2

 

즉 시간복잡도는 $O(\frac{n(n-1)}{2}) =$ $O(n^2)$ 이 됩니다.