[알고리즘] 단순 삽입 정렬 (Straight Insertion Sort)

선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘.

 

두번째 요소부터 선택하여 진행한다.

 

아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입하는 작업을 n - 1회 반복한다.

// 단순 삽입 정렬
void insertion(int a[], int n) {
    int i, j;
    for(i = 1; i < n; i++) {
        int tmp = a[i];
        
        for(j = i; j > 0 && a[j - 1] > tmp; j--) {
            a[j] = a[j - 1]; // 밀어내기
        }
        a[j] = tmp; // 밀어내고 남은 곳에 넣기
    }
}

 

떨어져 있는 요소들이 서로 뒤바뀌지 않아 알고리즘이 안정적이다.

 

시간복잡도 : O(n^2)

 

 

단순 삽입 정렬 알고리즘 개선 - 1, 보초법

 

단순 삽입 정렬에서 배열의 첫 번째 요소(a[0])부터 데이터를 저장하지 않고 a[1] 부터 데이터를 저장하여 a[0]을 보초로 세운다.

이렇게 함으로써 삽입을 마치는 조건을 줄일 수 있다.

// 단순 삽입 정렬 & 보초법
void insertion(int a[], int n)
{
    int i, j;

    for (i = 1; i < n; i++) {
        int tmp = a[0] = a[i];
        for (j = i; a[j - 1] > tmp; j--) {
            a[j] = a[j - 1];
        }
        a[j] = tmp; // 설명에 if(j)로 감싸져있었는데, j가 0인 경우는 실행되는 없으므(j=1일때 a[0] > tmp가 성립이 안되므로 무조건 탈출)로 쓸데없는 것 같아서 지움.
    }
}

 

 

단순 삽입 정렬 알고리즘 개선 - 2, 이진 삽입 정렬 (Binary Insertion Sort)

 

단순 삽입 정렬은 배열의 요소 개수가 많아지면 많아질수록 요소 삽입에 필요한 비교, 대입 비용이 무시할 수 없을 정도로 커진다.

배열에서 이미 정렬된 부분은 이진 검색을 사용하여 삽입할 위치를 빨리 찾을 수 있다.

// 이진 검색 + 단순 삽입 정렬 = 이진 삽입 정렬(binary insertion sort). 안정적이지 않은 알고리즘(이진검색이 들어가서).
void insertion(int a[], int n) {
    int i;
    for(i = 1; i < n; i++) {
        int tmp = a[i];
        
        // 아래 if문을 만족하지 않을 경우엔 그냥 값을 그대로 냅둠. 책의 이전 예제들처럼 제자리 교환작업(i = j일 때, int tmp = a[i]; a[j] = tmp;)을 불필요하게 수행하지 않음.
        if(a[i - 1] > tmp){
            
            int pl = 0; // 검색 범위 맨 앞의 인덱스
            int pr = i - 1; // 검색 범위 맨 끝의 인덱스
            int pc; // 검색 범위 가운데의 인덱스

            do {
                pc = (pl + pr) / 2;
                if(a[pc] == tmp) { // 같은값이 있을 때
                    // 흐름을 들어가보니, pl <= pr 을 만족하지 못하고 while문이 종료될 때 pl 자리가 값이 들어갈 자리더라(pl or pr+1). 난 pl로 지정하기로 했으니 여기서도 pl에 넣어줌.
                    pl = pc; break;
                }
                else if(a[pc] < tmp)
                    pl = pc + 1;
                else
                    pr = pc - 1;
            } while(pl <= pr);
            
            //분석해보니 while문이 탈출될 때의 pl값이 tmp값이 들어갈 자리인 것을 알게됌. // pl or pr+1
            
            // 밀어내는 작업
            for(int z=i; z > pl; z--) {
                a[z] = a[z-1];
            }
            // 참고로, 밀어내는 작업을 memmove를 쓰면 더 비용이 절감됨
            // memmove(a+pl+1, a+pl, sizeof(int)*(i-pl)); 메모리단위의 데이터 이동 함수, for문을 통해 요소를 뒤쪽으로 미는 작업보다 비용이 적지만 결과는 동일하여 좋음. memmove(dest, src, size) 형식을 갖는다.

            a[pl] = tmp; // 책의 이전 예제들과 달리 내 코드는 교환작업이 필요한 이 if문 안에서만 코드를 넣음으로써, a[i - 1] > tmp 가 아닐 경우엔 불필요한 제자리 체인지를 안해줌.
        }
    }
}

 

참고로 이 알고리즘은 안정적이지 않다(이진 검색이 들어가서)