| 해결할문제–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’sposition 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();
'프로그래밍' 카테고리의 다른 글
관련글
-
-
-
-
댓글