[C/C++]정렬 - 삽입정렬 insertion sort

자료구조

삽입정렬은 선택정렬과 유사하게 동작합니다.

 

다른 점은 정렬되어있는 리스트에 새로운 값을 찾아내 올바른 위치에 삽입한다는 것이죠.

 

삽입한다는 것을 전제로 하기 때문에 첫번째 원소를 왼쪽 배열의 기준으로 사용합니다. 삽입정렬이 실제로 진행되는 건 두번째 원소부터입니다.

 

void sort_insertion(int list[], int n){
    int i, j, key;
    for(i=1; i<n; i++){
        key = list[i];
        for(j=i-1;j>=0&&(list[j]>key);j--){
            list[j+1]=list[j];
        }
        list[j+1]=key;
    }
}

두번째 값부터 삽입의 대상이됩니다. 내부 for문은 j == 0 까지 돕니다. 비교자체는 j == -1 까지 하겠네요.

 

내부 for문은 삽입 될 배열을 훑으면서 삽입대상이 작으면 비교한 위치의 값을 현재위치 +1 에 값을 넣습니다. 이때 주목할 점은 배열을 훑을 때 삽입대상을 기준으로 잡아서 역방향으로 훑습니다.

 

공책에 살짝 메모를 해봤습니다.

 

▣복잡도 분석

삽입정렬의 경우에 이미 정렬되어 있다면 내부 for문을 돌지 않고 비교 한 번에서 그칩니다. 그렇기 때문에 n-1번의 비교가 실행되며, 외부 for문에 대입연산(이동연산)이 2개가 되므로 2(n-1)이 됩니다.

 

즉, 정렬된 상태라면 O(n)이 됩니다.

 

역순으로 정렬된 상태라면 내부루프는 n-1반복을 돌게 됩니다. 이게 외부 for문과 함께 돌면 (n(n-1))/2가 비교연산의 횟수이며, 이동횟수는 아까 구해놨던 2(n-1)이 됩니다. 

 

두개를 더하면 최종적으로 O(n²)이 됩니다.

 

삽입정렬의 경우 삽입대상을 기준으로 역순으로 돌기 때문에 안정성을 유지합니다. 순서가 뒤바뀌지않게 되는 것이죠.

 

 

"댓글, 공감 버튼 한 번씩 누르고 가주시면 큰 힘이 됩니다"