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