삽입정렬

삽입정렬

해결할 문제 – n개의 요소로 구성된 배열 A를 정렬하자 §초기_A – Loop A의 카운터 i에 1을 대입 §Loop _A( i <n)  //Loop invariant : A[0]~A[i-1] must be sorted §    temp에 A[i]를 대입 §    초기B- Loop_B의 카운터 j에 i를 대입 §    Loop_B (A[j-1] >temp and  j> 0) //Loop invariant: temp’s position is at A[0]-A[j] §        swap A[j],A[j-1] §        j assign  j-1 §    A[j] assign temp       i assign i+1   수행속도 i번째 요소를 자기 위치에 보내기 - LoopB의 수행속도 :T'(n) T('n) 은 최악의 경우 n-1번 비교한다. 삽입 정렬 - T(n) T(n) = T'(1) +  T'(2) + ... + T'(n)        = 0 + 1 + ... + (n-1) 즉 O(N*N)이다.    하지만 배열에 데이터를 순차적 보관을 하면서 보관하는 기능을 수행한 횟수가 10의 배수일때마다 자동으로 삽입 정렬을 수행하게 프로그래밍을 했다면 각 순간에 필요한 수행속도는 T(n) = T'(n-9) + T'(n-8) + ... +T'(n) 즉 O(N)이 될 수 있다.   삽입 정렬을 일반적인 수행속도 O(N*N)이라는 것보다 위와 같이 특수한 경우에 O(N)이 될 수 있으 므로 위와 같은 형태로 프로그래밍을 할 수 있는 경우에는 아주 바람직한 선택이 될 수 있다.  Array:  27 8  12  15  23  9  6  25  17 1:        8  27  12  15  23  9  6  25  17 2:        8  12  27  15  23  9  6  25  17 3:        8  12  15  27  23  9  6  25  17 4:        8  12  15  23  27  9  6  25  17     4-a: 8  12  15  23  9  27  6  25  17     4-b: 8  12  15  9  23  27  6  25  17     4-c: 8  12  9  15  23  27  6  25  17     4-d: 8  9  12  15  23  27  6  25  17 5:        8  9  12  15  23  27  6  25  17 6:        6  8  9  12  15  23  27  25  17 7:        6  8  9  12  15  23  25  27  17 end:    6  8  9  12  15  17  23  25  27

 

다음은 정수형 배열의 예를 든 삽입정렬 코드입니다.

#include <stdio.h> #include <conio.h> void Swap(int *a,int *b) {     int temp = *a;     *a = *b;     *b = temp; } void FindSeat(int *base,int now) {     for( ; now ; now--)     {         if(base[now-1] > base[now])        {           Swap(base+now-1,base+now);        }       else       {           break;       }    } } void InsertSort(int *base,int asize) {     int i ;     for(i = 1; i<asize;i++)    {          FindSeat(base,i);    } } void main() {     int arr[10] = {8,6,9,10,4,3,7,5,1, 2};     int i = 0;     printf("Sorting전");     for( ; i<10; i++)    {         printf("%d ",arr[i]);    }    printf("\n");    InsertSort(arr,10);    printf("Sorting후");    for(i=0 ; i<10; i++)    {        printf("%d ",arr[i]);    }    printf("\n");    printf("아무키나 누르세요\n");    getch(); }