[알고리즘] 삽입 정렬 알고리즘

삽입 정렬의 기본적인 연산은 데이터가 정렬되어 있을 때 이들 데이터 사이의 적당한 위치에 맞는 데이터를 삽입하는 것이다. 데이터를 삽입하고 난 뒤 그보다 오른쪽에 있던 데이터는 오른쪽으로 하나씩 자리를 옮겨줘야 한다.

 

삽입 정렬은 두 번째 데이터부터 정렬을 시작해 그 앞에 있는 데이터와 비교하고 삽입할 위치를 찾은 뒤 삽입할 위치의 공간 확보를 위해 데이터를 오른쪽으로 옮겨준 뒤 삽입하게 된다.

 

for(i=2 ; i<n ; i++) {
    w = a[i];
    j=i-1;
    while((w<a[j])&&(j>=0)) {
        a[j+1] = a[j];
        j = j-1;
    }
    a[j+1] = w;
}

w가 삽입할 데이터이다. (a[0]은 없고 배열은 a[1]부터 시작한다고 침.)

코드만 보면 무슨 소린지 모르겠으니까 직접 데이터 배열로 정렬해보며 알아보자.

초기 상태가 [ 21  34  4  54  29  17 ]인 데이터 배열이 있다.

 

-첫번째 반복

for반복문에 들어서면 w = a[2]이므로 w=34이고,  j= i-1이므로 j=1이 된다.

while문에 들어가게 되면 w가 a[1]보다 작으면서 동시에 j가 0보다 크거나 같을 때 까지 반복을 돌게된다. 조건문을 만족시키지 못 하기 때문에 반복문을 돌지 않고 종료된다. a[j+1] = w 는 a[2] = 34로 첫번째 for문 종료. (배열상 변화 없음) [ 21  34  4  54  29  17 ]

 

-두번째 반복

두번째 반복을 돌아 i = 3일 때, w=a[3]이므로 w=4, j= 2일 때 w는 a[2]보다 작으므로 while문을 돌게 된다.

a[j+1] = a[j] 는 데이터를 오른쪽으로 옮겨주는 코드이기 때문에 a[3]에 a[2] 값을 넣어주게 된다. j=j-1이기 때문에 j=1이 된다.

여전히 while의 조건문인 w<a[1]을 만족하기 때문에 a[2] = a[1]로 데이터를 오른쪽으로 옮겨주고 j=0이 되며 while문을 빠져나온다.

마지막으로 a[j+1] = w이기 때문에 a[1] = 4로 데이터를 삽입하게 된다. 바뀐 배열은 [ 4  21  34  54  29  17 ]이 된다.

이를 반복하다보면 최종적으로 [ 4  17  21  29  34  54 ]로 오름차순으로 잘 정렬된 것을 볼 수 있다.

 

 

 

참고 : C언어로 작성하는 컴퓨터 알고리즘 / 이한출판사