<img src="http://blogimgs.naver.com/nblog/ico_scrap01.gif" class="i_scrap" width="50" height="15" alt="본문스크랩" /> 선택정렬

선택정렬

해결할문제–n개의요소로구성된배열A를정렬하자 §초기:A–Loop A의카운터i에0을대입 §Loop A( i <n-1) //safe location A,Loop invariant : A[0]~A[i-1] must befinded seat §    temp에i를대입 §    초기:B- Loop_B의카운터j에i+1를대입 §    Loop B (j<n) //safe location B,Loop invariant: temp is mimimum within A[i] toA[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(); }

 

반응형

'프로그래밍' 카테고리의 다른 글

<img src="http://blogimgs.naver.com/nblog/ico_scrap01.gif" class="i_scrap" width="50" height="15" alt="본문스크랩" /> 파서트리  (0)	2009.05.12
<img src="http://blogimgs.naver.com/nblog/ico_scrap01.gif" class="i_scrap" width="50" height="15" alt="본문스크랩" /> 삽입정렬  (0)	2009.05.12
<img src="http://blogimgs.naver.com/nblog/ico_scrap01.gif" class="i_scrap" width="50" height="15" alt="본문스크랩" /> 퀵소트  (0)	2009.05.12
<img src="http://blogimgs.naver.com/nblog/ico_scrap02.gif" class="i_scrap" width="50" height="15" alt="링크스크랩" /> 알고리즘 :: 정렬 - 퀵정렬.  (0)	2009.05.12
<img src="http://blogimgs.naver.com/nblog/ico_scrap02.gif" class="i_scrap" width="50" height="15" alt="링크스크랩" /> 알고리즘 :: 정렬 - 버블정렬.  (0)	2009.05.12