[프로그래밍] 삽입정렬(Insert Sort)이란?

* 이 자료를 퍼 가셔서 타사이트나 블로그에 게재 시 출처를 명시해 주시기 바랍니다.

  본 사이트에 게재된 모든 내용 및 자료는 상업적인 용도로 이용할 수 없습니다.

 

 

1. 삽입정렬(Insert Sort)이란?

-. 가장 왼쪽에 있는 첫번째 값을 이미 정렬된 상태로 가정하고 나머지 자료들을 정렬한다.

-. 두번째 값을 기준으로 첫번째 값을 비교하여 값에 따라 순서대로 나열하며, 세번째 값을

   기준으로 두번째 값과 첫번째 값을 비교하여 값에 따라 순서대로 나열한다.

   위와 같은 방법으로 n - 1개의 값과 비교하여 삽입될 적당한 위치를 찾아 삽입한다.

-. 이미 정렬이 된 부분에 새로운 값을 적절한 순서에 삽입하는 동작을 반복적으로 하는 정렬이다.

-. 적은 비교와 많은 교환이 필요한 방법이므로 소량의 자료를 처리하는데 가장 유리한다.

 

2. 삽입정렬을 이용하여 오름차순으로 정렬하는 방법

 

3. 삽입정렬의 비교회수

-. 최선일 경우의 비교회수 공식 : N - 1

-. 최악일 경우의 비교회수 공식 : N(N – 1)/2

-. 위의 그림을 보시면 아시겠지만 제일 처음에는 (N – 1)번을 비교하고,

   그 다음에는 (N – 2)번 만큼 비교하고, 그 다음은 (N – 3)번을 비교하면서 비교회수가 1이 될

   때까지 이 작업을 반복할 것이다.

-. 비교회수는 (N – 1) + (N – 2) + (N – 3) …… + 1 이 될 것이다.

   최대 (N – 1)번을 수행할 것이며, 각 패스가 수행할 때마다

   수학식으로 표현하면    이므로 공식은 N(N – 1)/2 이런 공식이 성립된다.

-. 5개의 값을 오름차순으로 선택정렬을 하면

   공식에 의해서 5(5 – 1)/2 = 10 가 성립된다.

   즉, 총 10번의 비교를 통해서 오름차순으로 정렬된 값을 볼 수 있다.

 

4. 삽입정렬의 연산시간

   -. 연산시간 공식 : O(n²)

-. 연산시간을 표기하는 방법은 일반적으로 사용하는 O표기법인데, 이 O표기법은 ‘최악의 경우’

   (Worst Case)에 대한 연산시간을 나타낸다.

-. 수학식으로 표현하면 아래와 같다.

     = n(n – 1) – (n – 1)/2 = n(n - 1)/2 이므로 Worst Case는 n(n – 1)/2 이다.

   그래서 연산시간은 O(n²)가 되는 것이다.

  

5. 삽입정렬의 장점

-. 정렬된 값은 교환이 한번도 일어나지 않고 비교만 n- 1번 하게 된다. (그래서 속도가 빠르다.)

 

6. 삽입정렬의 단점

-. 입력자료(정렬되어 있는 자료인지 아니면 역순의 자료인지)에 민감하다.

-. 역순일 때는 교환과 비교의 회수가 N(N – 1)/2번이 되는 최악의 경우이므로 선택정렬보다

   속도가 떨어진다.

 

7. 삽입정렬을 이용해서 작성한 예제

#include "stdio.h"   void Insert_Sort(int parm_data[], int parm_count) {     int i, temp, move_index;     int comparison_count = 0;       for(i = 1; i < parm_count; i++){          temp = parm_data[i];          move_index = i - 1;            comparison_count++;          while(move_index >= 0 && parm_data[move_index] > temp){              parm_data[move_index + 1] = parm_data[move_index];              move_index--;          }          parm_data[move_index + 1] = temp;      }      printf("총 비교회수는 [ %d 회] 이다.", comparison_count);      printf("\n\n\n");   }   void main() {     int array[5] = {7, 4, 11, 9, 2};     int i;       printf("=== 삽입정렬하기 전 ===\n\n");     for(i = 0; i < 5; i++) printf("%d   ", array[i]);     printf("\n\n");     printf("================================");     printf("\n\n");       Insert_Sort(array, 5);     printf("=== 삽입정렬한 후 ===\n\n");     for(i = 0; i < 5; i++) printf("%d   ", array[i]);     printf("\n\n"); }

 

 

결과는 아래와 같습니다.

출처 : http://www.tipssoft.com/bulletin/board.php?bo_table=FAQ&wr_id=61