삽입 정렬(Insertion Sort) - C언어/자료구조

'맞는 위치에 삽입시켜가며 정렬하는 삽입정렬'

 

삽입정렬은 Insertion Sort라고도 부르며 데이터 정렬 방법 중 하나입니다.

 

 

키(key) 값을 가지고 정렬시키는 삽입 정렬은 두 번째 자료부터 시작하여

그 앞의 자료들과 비교하여 알맞은 위치로 삽입하는 형태의 정렬입니다.

(배열로 보는 경우 삽입이라면 뒤의 자료들은 한 칸씩 밀리는 형태가 되겠죠?)

(아래 데이터 이동 그림을 보시면 이해하시기 더 좋을 것이라 생각됩니다.)

 

여러 회전을 반복하여 정렬하는 방법입니다.

 

첫 번째 회전에서는

 두 번째 자료를 키 값으로 가지고 앞의 자료들을 하나씩 비교합니다.

 두 번째 자료의 앞 자료는 첫 번째 자료 하나밖에 없으니 하나만 확인하면 됩니다.

 첫 번째 자료가 키 값보다 크다면 두 번째 자료를 첫 번째 자료로 바꿔줍니다.

 (작다면 바꿀 필요 없이 그대로 두면 되겠죠?)

 더 이상 비교할 대상이 없으니 첫 번째 자료 위치에 키 값을 넣어줍니다.

 

두 번째 회전에서는

 세 번째 자료를 키 값으로 가지고 앞의 자료들을 하나씩 비교합니다.

 세 번째 자료의 앞 자료는 두 번째, 첫 번째 자료 두 개가 있죠?

 두 번째 자료가 키 값보다 크다면 세 번째 자료를 두 번째 자료로 바꿔줍니다.

 (작다면 바꿀 필요 없이 그대로 검사를 종료하고 그대로 위치합니다.)

 다음으로 첫 번째 자료와 키 값을 비교합니다.

 첫 번째 자료가 더 크다면 두 번째 자리에 첫 번째 자료를 넣어줍니다.

 (작다면 바꿀 필요 없이 그대로 검사를 종료하고, 키 값을 두 번째 자리에 위치시켜주면 되겠죠?)

 더 이상 비교할 대상이 없으니 첫 번째 자료 위치에 키 값을 넣어줍니다.

 

세 번째, 네 번째 회전 모두 앞의 회전과 같은 방식으로 진행됩니다.

5개라면 4 회전, 10개 라면 9회전 n-1회전 만큼 진행됩니다.

 

 

 

실제로 5개의 숫자 배열 자료가 어떻게 정렬되는지 확인해볼까요?

 

 

7, 4, 10, 3, 5 다섯 숫자를 가지고

삽입정렬 하는 과정을 보도록 하겠습니다.

 

 

1 회전

가장 먼저 두 번째 자리의 4를 키 값으로 가지고 앞의 자리를 비교합니다.

앞의 자리는 첫 째 자리 하나밖에 없죠?

 

비교 결과 키 값인 4가 첫 째 자리의 7보다 작기 때문에

첫 째 자리의 7은 두 번째 자리로 이동하고

키 값은 더 이상 비교 대상이 없기 때문에 남은 자리(첫 째 자리)로 들어갑니다.

 

 

2 회전

두 번째 회전에서의 키 값은 세 번째 자리의 10이 됩니다.

그리고 바로 앞의 자리인 두 번째 자리의 7과 비교합니다.

 

비교 결과 키 값인 10보다 두 번째 자리의 7이 더 작기 때문에

현재 위치로 키 값의 자리가 결정됩니다.

 

 

3 회전

세 번째 회전에서의 키 값은 네 번째 자리의 3이 됩니다.

그리고 바로 앞의 자리인 세 번째 자리의 10과 비교합니다.

 

비교 결과 키 값인 3보다 세 번째 자리의 3이 더 크기 떄문에

네 번째 자리에 10을 넣어줍니다.

(아직 3의 자리는 확정되지 않았죠? 더 비교해야 합니다.)

 

편의상 교환이라고 적어뒀지만 실제로는 교환이 아니라 이 전의 값이 들어있습니다.

실제로 데이터를 비교하여 작은 값을 만나 확정되면 그 자리에 들어갑니다.

 

다음으로 키 값인 3과 두 번째 자리의 7을 비교합니다.

 

비교 결과 키 값인 3보다 두 번째 자리의 7이 더 크기 때문에

세 번째 자리에 7을 넣어줍니다.

 

(작은 값을 만나거나 마지막 자리 검사할 때까지 계속 검사는 이어집니다.)

 

다음으로 키 값인 3과 첫 번째 자리의 4를 비교합니다.

 

비교 결과 키 값인 3보다 첫 번째 자리의 4가 더 크기 때문에

두 번째 자리에 4를 넣어줍니다.

 

그리고 첫 번째 자리까지 시작 지점으로부터 모든 앞 자리를 모두 검사했기 때문에

검사를 종료하고 해당 위치에 키 값인 3을 넣어줍니다.

 

 

4 회전

5개 배열에서의 마지막 회전으로 키 값은 다섯 번째 자리의 5입니다.

키 값인 5와 바로 앞의 자리인 네 번째 자리의 10을 비교합니다.

 

비교 결과 키 값인 5보다 네 번째 자리의 10이 더 크기 때문에

다섯 번째 자리에 10을 넣어줍니다.

 

 

다음으로 키 값인 5와 세 번째 자리의 7을 비교합니다.

 

비교 결과 키 값인 5보다 세 번째 자리의 7이 더 크기 때문에

네 번째 자리에 7을 넣어줍니다.

 

 

다음으로 키 값인 5와 두 번째 자리의 4를 비교합니다.

 

비교 결과 키 값인 5보다 두 번째 자리의 4가 더 작기 때문에

4의 위치는 그대로이며 키 값의 위치가 결정되었습니다.

 

 

이렇게 삽입 정렬은 시작 지점부터 앞으로 하나씩 검사하며

자신이 지정한 조건이 만족할 때까지 반복됩니다.

정렬들은 조건 부분을 알맞게 바꿔주면 오름차순, 내림차순 모두 가능하겠죠?

 

 

 

 

 

 

 

그럼 이번에는 C 프로그램으로 삽입 정렬을 확인해볼까요?

(소스는 제공하지만, 위의 과정을 보고 직접 만들어 보시면 좋을 것 같네요.)

 

 

출력 결과 예를 보고

프로그램의 소스를 작성해보세요.

 

 

(출력 결과 예)

 

 

 

 

 

제가 완성한 소스입니다.

 

 

보고 참고하세요.

 

 

(복사할 수 있는 소스는 아래 전체복사용소스보기를 누르시면 됩니다.)

 

 

 

 

 

#include<stdio.h>
//Prosto
int main(void) {
 int data[10] = { 10, 6, 7, 9, 3, 4, 2, 1, 5, 8 };
 int keyValue;
 int j; //키 값의 위치를 for문 반복 종료되는 시점으로 판별하기 위해.
 //랜덤한 위치라고 생각.
 printf("정렬 전 순서\n"); //정렬하기 전 상태 출력.
 for (int i = 0; i < 10; i++) {
  printf("%d ", data[i]);
 }
 printf("\n");
 //아래의 2중 for문이 삽입 정렬 핵심.
 for (int i = 0; i < 9; i++) { //10-1번 회전.
  keyValue = data[i + 1]; //키 값.
  for (j = i; j > -1; j--) { //키 값이 위치한 부분의 바로 앞부터 배열 0번까지 진행.
   if (data[j] > keyValue) { //오름차순이니 작은지 확인.
    data[j + 1] = data[j]; //항상 한 칸 위에서 비교해보니.
   }
   else {
    break; //앞, 더 이상 검사x.
   }
  }
  //참고로 j+1인 이유는 종료된 시점보다 한 칸 앞이기 떄문에
  //추가적으로 마지막에 j--로 넘어오기 때문에 j=-1인 상태, 0번에 넣으려면 j+1이 필요.
  data[j + 1] = keyValue; //더 이상 작은 값을 발견하지 못 했으니 그 바로 앞 위치가 키값이 들어갈 위치.
 }
 printf("정렬 후 순서\n"); //정렬한 후 상태 출력.
 for (int i = 0; i < 10; i++) {
  printf("%d ", data[i]);
 }
 printf("\n");
 return 0;
}

 

 

궁금한 점 있으시면 댓글이나 따로 메일로 질문하시면 시간되는 대로 답변드리겠습니다. ( 연락 )