Insertion Sort (삽입 정렬)

알고리즘

삽입 정렬의 주요 아이디어는, 원소를 맞는 위치로 옮기고 나머지 원소들을 밀어내는 것이다.
먼저 첫번째 원소는 정렬된 것으로 생각하며, 두번째 원소부터 연산을 시작하게 된다.

각 패스마다 n번째 원소를 기준으로 잡는다.

기준이 된 원소는 데이터를 임시로 저장해놓는다.

n-1번째 원소부터 역으로 첫번째 원소까지 검사를 시작한다.

만약 검사대상이 현재 기준이 되는 값보다 큰 경우 검사대상을 한칸 뒤로 보낸다.

여기서 뒤로 보낸다는 의미는, Index를 하나 키운다는 것으로,

다른 값들을 차례차례 덮어씌운다. 

예를들어 다음과 같은 원소들이 있다고 가정하자.

3, 7, 2, 6, 9, 1

첫번째 패스에서는 7을 기준으로 잡는다.

7은 임시 저장소에 저장이 되므로, 다른 값으로 덮어씌워도 상관이 없다.

7 앞에 있는 원소는 3이며, 이 숫자는 7 보다 작기 때문에, 순서가 바뀔 필요가 없다.

즉 3을 7이 있는 자리에 덮어 씌울 필요가 없다.

for문을 사용한다면, 작은 숫자를 발견했을때 루프를 중단시켜버리면 된다.

이것이 루프 중단 조건 첫번째가 된다.

두번째 패스에서는 2를 기준으로 잡을 것이다.

마찬가지로 2는 임시 저장소에 저장이 된다.

2 앞에 있는 원소는 7이므로, 이 숫자는 2 보다 크기 때문에, 순서를 한칸 뒤로 당겨온다.

이 때의 원소의 배열은 아래와 같다.

3, 7, 7, 6, 9, 1

2의 값이 사라져버렸지만, 우리는 2를 임시 저장소에 넣어 두었기 때문에 걱정할 필요가 없다.

다음 3을 검사해 보면, 역시 2보다 크기 때문에 한칸 뒤로 빼 두어야 한다.

이 때의 원소의 배열은 아래와 같다.

3, 3, 7, 6, 9, 1

그 다음에는 검사할 원소가 없다. 즉 배열의 끝에 다다르게 되었다.

이 때가 루프 중단점의 두번째 조건이 된다.

루프가 중단된 이후에는, 임시저장된 데이터를 중단된 부분의 인덱스로 옮기면 된다.

따라서 최종적으로 패스가 완료되면,

2, 3, 7, 6, 9, 1

다음과 같은 정렬 상태를 갖게 된다.

이것이 바로 Insertion Sort 의 알고리즘이 되겠다.

코드

#include <stdio.h>

void insertion_sort(int num[],int len);
void tracer(int num[],int len);

int main(void){
    int testArr[] = {485,241,454,325,452,685,498,890,281};
    int len = sizeof(testArr)/sizeof(int);
    insertion_sort(testArr,len); // 삽입 정렬 함수 호출
}

void insertion_sort(int num[],int len){
    int i,j,tempINT;
    for(i = 1; i < len; i++){ // 1번째 원소는 정렬된 것으로 간주함 (검사안함)
        tempINT = num[i]; // 해당 번째 원소를 임시로 저장
        for(j = i-1; num[j] > tempINT && j >= 0; j--){  
            // 임시 저장된 값과 비교를 해서 작은 값이 나올 때 까지 계속 검사
            // 배열의 끝까지 검사
            num[j+1] = num[j]; // 원소를 한 칸씩 밀어냄
        }
        num[j+1] = tempINT; // 검사가 끝난 인덱스에 임시저장 원소를 대입
        tracer(num,len);
    }
}

void tracer(int num[],int len){
    int i;
    for(i=0; i<len ;i++){
        printf("%d\t",num[i]);
    }
    printf("\n");
}

결과