09 삽입 정렬

9.1 삽입 정렬 소개

  삽입 정렬이란, 배열의 왼쪽 끝의 숫자를 정렬이 끝났다고 간주한다. 그리고 아직 작업하지 않은 숫자 중에서 왼쪽 끝에 있는 숫자를 꺼내서 왼쪽에 있는 작업이 끝난 숫자와 비교한다. 왼쪽의 숫자가 크다면 두 개의 숫자를 바꾼다. 이 작업을 자신보다 작은 숫자가 나타나거나 왼쪽 끝에 도달할 때까지 반복하여 정렬하는 방법이다. 말 그대로 삽입 정렬은 가장 왼편의 값을 정렬이 완료되어 있는 값으로 보고 나머지 요소들을 하나씩 꺼내와 정렬되어 있다고 가정한 왼편의 요소들과 비교하여 정렬되어야 하는 위치에 삽입하는 방식이다.

 

의사코드

1. 배열의 두 번째 요소를 선택하여 반복을 시작한다.(왜냐하면 가장 앞에 있는 요소는 정렬이 완료되었다고 간주하기 때문이다.)

2. 그 다음 두 번째 요소를 취하여 앞에 있는 값과 비교한다. 그리고 앞에 있는 값이 더 크다면 두 값을 스왑한다.

3. 이 과정을 반복한다.

 

9.2 삽입 정렬 구현

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

  반복되는 j는 이미 정렬이 완료된 왼쪽의 요소들을 반복시켜주는 것이다. 그렇기에 j는 비교하기 위해 꺼내진 i인덱스를 가진 요소의 인덱스에 -1을 한 값부터 시작되는 것이고 j는 0번 인덱스보다는 커야 하므로 조건을 만들었고, j의 값이 현재 비교하고자 꺼내놓은 값보다 큰 경우에 스왑이 일어나는 것이다. 그리고 만약 중첩 반복문 루프가 돌다가 조건식이 false인 경우에는 튕겨져 나온 j는 정렬이 된 부분을 가리키기 때문에 j+1을 하여 presentValue 값을 할당해 준다. 

 

9.2 빅오 표기법 비교

지금까지 배운 일반적인 정렬들인 버블 정렬, 선택 정렬, 시간 정렬의 빅오 표기법을 비교해 보자면

알고리즘	시간 복잡도(Best)	시간 복잡도(Average)	시간 복잡도(Worst)	공간 복잡도
버블 정렬	O(n)	O(n^2)	O(n^2)	O(1)
선택 정렬	O(n)	O(n^2)	O(n^2)	O(1)
삽입 정렬	O(n^2)	O(n^2)	O(n^2)	O(1)

  가장 베스트인 경우에는 O(n)시간 복잡도 까지 나오는 정렬 알고리즘도 존재하지만 평균적으로는 O(n^2)의 시간 복잡도를 갖는다. 이말은 다시 말하면 그렇게 효율적이지 않다는 것이다. 앞으로 배울 정렬 알고리즘들과 비교해 본다면 얼마나 비효율적일 수 있는지 정확하게 알 수있다.