선택정렬

선택정렬

해결할 문제 – n개의 요소로 구성된 배열 A를 정렬하자 §초기: A – Loop A의 카운터 i에 0을 대입 §Loop A( i <n-1)  //safe location A, Loop invariant : A[0]~A[i-1] must be finded seat §    temp에 i를 대입 §    초기:B- Loop_B의 카운터 j에 i+1를 대입 §    Loop B (j<n) //safe location B, Loop invariant: temp is mimimum within A[i] to A[j] §        if(A[temp]>A[j]) §            temp assign j §        j assign j+1 §    swap A[i],A[temp]        §     i assign i+1     수행 속도 n개의 자료 중 최소값 찾기 - 루프 B 수행 속도 T'(n)  T'(n) = n-1 번 비교 선택 정렬 - 전체 수행 속도: T(n)  T(n) = T'(n)+T'(n-1)+T'(n-2)+...+T'(1)        = (n-1) + (n-2) + ( n-3) + ... + 0        = 1/2N*N + 1/2 ==> O(N*N)    예: Array:  27 8  12  15  23  9  6  25  17 1:        6  8  12  15  23  9  27  25  17 2:        6  8  12  15  23  9  27  25  17   2-a:   6  8  12  15  23  9  27  25  17                      i      j                     min  2-b:   6  8  12  15  23  9  27  25  17                      i          j                     min                            2-c:   6  8  12  15  23  9  27  25  17                      i               j                                    min  2-d:   6  8  12  15  23  9  27  25  17                      i                    j                                    min  2-e:   6  8  12  15  23  9  27  25  17                      i                          j                                    min  2-f:   6  8  12  15  23  9  27  25  17                      i                               j                                    min 3:        6  8  9  15  23  12  27  25  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; } int *FindMin(int *base,int now) {     int i = 0;     int *min_pos = base;     for( ; i<now ; i++)     {          if(*min_pos > base[i])          {               min_pos = base+i;          }     }     return min_pos;   } void SelectSort(int *base,int asize) {     int i ;     int *min_pos = 0;     for(i = 0; i<asize;i++)     {          min_pos = FindMin(base+i,asize-i);          Swap(min_pos,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");     SelectSort(arr,10);     printf("Sorting후");     for(i=0 ; i<10; i++)     {          printf("%d ",arr[i]);     }     printf("\n");     printf("아무키나 누르세요\n");     getch(); }