삽입정렬 (Insertion Sort)

​- 삽입정렬(Insertion Sort) -

 

정렬을 수행할 위치(i)의 값을 저장(tmp)하고

미리 정렬된 왼쪽 부분(j) 중 적절한 위치에 삽입하는 정렬

 

---

 

문제인식)

다음 그림과 같은 수(數)의 배열이 있다.

int a[10] = {10, 2, 1, 9, 7, 4, 5, 8, 6, 3};

이 배열을 오름차순 정렬, 즉 가장 작은 수부터 차례대로 정렬하기 위해선 어떻게 프로그래밍 해야할까?

 

---

 

해결과정)

0) 아래 그림은 이미 4번의 정렬이 이뤄졌다고 가정한 상태이다.

즉, 5번째의 정렬이 이뤄져야 할 상태이며, 4번째 원소까지는 이미 오름차순 정렬이 되어있는 부분이다.

 

1) 정렬을 수행할 위치를 선정하고 그 값을 저장한다.

2) 왼편에 있는 원소들이 저장한 값보다 크다면 한 칸씩 뒤로 밀어둔다.

3) 적절한 자리를 찾으면 저장값을 배치한다.

 

(※ [더보기]를 클릭하면 C/C++ 소스코드를 참조할 수 있습니다.)

int n, i, j, tmp;
int a[10] = {10, 2, 1, 9, 7, 4, 5, 8, 3, 6};

n=10; //배열의 크기 

for(i=1; i<n; i++) {
    tmp=a[i];
    for(j=i-1; j>=0; j--) {
        if(a[j]>tmp) {
            a[j+1]=a[j];
        }
        else break;
    }
    a[j+1]=tmp;
}

 

맨 처음 시작할 때, i는 0이 아닌 1로 초깃값을 설정하였다.

그 이유는 첫번째의 원소 하나가 이미 정렬되어 있다고 가정한 상태에서 시작하기 때문이다.

나중에 첫번째 원소도 정렬이 이뤄질수록 뒤로 밀리게 되면서 제자리를 찾아가기에 문제될 건 없다.

 

j는 왼편의 원소들을 뒤로 한 칸씩 밀었을 때와,

적절한 자리를 찾아넣을 때에도 이용되었다.

 

tmp를 a[j+1]에 넣은 이유는

안쪽 for문을 보면 j--로 인해서 적절한 위치보다 한 칸 더 감소했기 때문이다.

 

메인 함수와 출력까지 나타낸 최종 코드는 다음과 같다.(C/C++)

#include <stdio.h>

int main() {
    int n, i, j, tmp;
    int a[10] = {10, 2, 1, 9, 7, 4, 5, 8, 3, 6};

    n=10; //배열의 크기 

    for(i=1; i<n; i++) {
        tmp=a[i];
        for(j=i-1; j>=0; j--) {
            if(a[j]>tmp) {
                a[j+1]=a[j];
            }
            else break;
        }
        a[j+1]=tmp;
    }

    for(i=0; i<n; i++) {
        printf("%d ", a[i]);
    }
	
	return 0;
}

 

---

 

응용)

내림차순 정렬해보기,

 

왼편이 아닌 오른편이 이미 정렬되어 있다고 가정해보기,

 

LRU(Least Recently Used)

 

등