[정렬 알고리즘]Insertion Sort

삽입 정렬 알고리즘(Insertion Sort Algorithm)

앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입해서 배열의 정렬된 부분을 점진적으로 구축하는 알고리즘이다.

 

 

왜 삽입 정렬인지 애니메이션을 통해 알 수 있다. 한 번에 하나를 취해서 올바른 위치에 삽입하는 것이다.

 

 

 

 

 

 

 

 

 

 

 

의사코드

1. 배열의 두 번째 요소를 선택하여 시작한다. 왜냐하면 첫 번째 요소는 정렬된 부분으로 간주하기 때문이다.

2. 앞의 요소와 비교하고 필요하면 swap한다.

3. 다음 요소로 계속 이동한 후 순서가 잘못된 경우, 정렬된 부분을 반복하여 요소를 올바른 위치에 배치한다.

4. 배열이 정렬될 때까지 반복한다.

 

삽입 정렬 구현 과정

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let currentVal = arr[i];
        for(let j = i-1; j >= 0; j--) {
            console.log(i, j)
        }
    }
    return arr
}

insertionSort([2,1,9,67,5])

실행 결과

해당 중첩 loop가 왜 저렇게 짜여졌는지, 실행 결과를 보면서 스스로 이해해보자.

앞으로 이루어져야할 것은 무엇인지에 대해서도 생각해보자. 

 

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let currentVal = arr[i];
        for(var j = i-1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j+1] = arr[j]
        }
        arr[j+1] = currentVal;
    }
    return arr
}

insertionSort([2,1,9,67,5])

정상적으로 동작하는 코드이다. currentVal는 삽입이 발생할 항목이며 arr[j]가 더 클 경우 loop가 지속된다. 

위 코드의 이해를 돕기위해 [1,2,9,55,20]에서 20을 삽입 해야한다. 즉, currentVal가 20일때, j는 3 즉, 55이다. 

loop내부의 동작 arr[j+1] = arr[j]으로 인해 [1,2,9,55,55]의 형태를 가지며 j는 -1하여 2가 즉, 9가 된다. 9는 55보다 작기 때문에 false가 되어 loop를 빠져나와 arr[j+1] = currentVal가 실행된다. 그렇기에 [1,2,9,20,55]의 정렬된 배열이 되는 것이다. 

 

삽입 정렬의 Big O 복잡도

삽입 정렬은 앞서 배운 두가지 정렬과 전반적으로 비슷하다. 완전히 reversed된 경우 최악이며, 데이터가 거의 정렬되어 있다면 꽤 좋다. 한가지 흥미로운 예시로 온라인에서 실시간으로 번호를 받는 코드가 있다고 한다면 삽입 정렬은 어떤 숫자가 입력되더라도 필요한 위치에 넣을 수 있다. 라이브, 스트리밍 방식으로 들어온 데이터를 즉시 입력해야하는 상황에 편리할 수 있다. 

 

Bubble Sort 👊 Insertion Sort 👊 Selection Sort

Algorithm	Time Complexity			Space Complexity
	Best	Average	Worst
Selection Sort	O(n)	O(n^2)	O(n^2)	O(1)
Bubble Sort	O(n)	O(n^2)	O(n^2)	O(1)
Selection Sort	O(n^2)	O(n^2)	O(n^2)	O(1)

이들을 기본 정렬 알고리즘 혹은 2차 정렬 알고리즘이라 한다. 앞으로 좀 더 어렵지만 성능적으로 우수할 수 있는 정렬들을 다루어볼 것이다.