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

1. 삽입정렬 (Insertion Sort)

삽입정렬은 배열의 모든 요소를 앞에서부터 차례로 비교하여 자신의 위치를 찾아 삽입하며 정렬하는 알고리즘이다. 

앞에 있는 요소들과 비교해야 하기 때문에 두 번째 인덱스부터 시작한다. 

평균적으로 O(n^2)의 시간복잡도를 갖는다.

 

 

 

2. 삽입정렬 구현

function solution(arr) {
    let answer = arr;

    for (let i = 1; i < arr.length; i++) {
        let tmp = arr[i], j;
        for (j = i - 1; j >= 0; j--) {
            if (arr[j] > tmp) arr[j + 1] = arr[j];
            else break;
        }
        arr[j + 1] = tmp;
    }

    return answer;
}

let arr = [11, 7, 5, 6, 10, 9];
console.log(solution(arr));

 

이제 자바스크립트에서 삽입정렬 구현하는 방법을 알아보자.

 

for (let i = 1; i < arr.length; i++) { ... }

 

위에서 얘기했듯이 삽입정렬은 앞에 있는 요소와 해당 요소를 비교하여 정렬한다.

따라서 for문의 시작 인덱스는 1이 된다. 

 

let tmp = arr[i], j;
    for (j = i - 1; j >= 0; j--) {
        if (arr[j] > tmp) arr[j + 1] = arr[j];
        else break;
    }
arr[j + 1] = tmp;

 

그 후 현재 요소를 담아놓을 tmp 변수를 만들어준다.

 

두 번째 for문은 i-1에서 0까지 돈다.

현재 요소 바로 앞에서 맨 처음 요소까지 모두 비교해야 하기 때문이다.

 

 

그 후 앞에 있는 요소가 현재 요소보다 크다면, arr [j+1]에 arr [j]의 값을 넣어준다.

즉, 비교 요소의 자리를 뒤로 한 칸 옮겨 준다.  

 

그리고 tmp를 해당 자리에 넣어준다.

for문이 j--이기 때문에 j의 값이 변했으므로 +1을 해줘야 한다.