선택정렬(Selection-Sort)

선택정렬(SelectionSort)

알고리즘의 복잡도는 O(n^2)

버블정렬과 비슷하지만 자료의 이동이 보다 적어 선택정렬이 효율이 좋다.

동작원리

- 배열의 첫원소를 key 값으로 설정하고 나머지 배열원소 중 가장 작은 원소를 찾아 교체한다. 

- 교체후에 첫 원소를 제외한 두번째 원소를 키값으로 나머지 배열중 가장 작은 원소 값을 찾아 교체한다.

- 이러한 방식으로 마지막 까지 교체를 한다면 정렬이 완료됨

소스

1. #include<stdio.h>
2.  
3. int main(void)
4. {
5.     int arr[5] = {5,4,3,1,2};
6.     int tmp  =  0;
7.     int tmp2 =  0;
8.     int key =   0;
9.     int keyin = 0;
10.     int dis =   0;
11.     int ch =    0;
12.  
13.     printf("전: ");
14.     for(dis = 0; dis<5;dis++)
15.     {
16.         printf("%d ",arr[dis]);
17.     }  
18.     printf("\n");
19.  
20.     for(tmp = 0;tmp<5;tmp++)
21.     {
22.         key = arr[tmp];
23.  
24.         for(tmp2 = tmp+1; tmp2 < 5 ; tmp2++)
25.         {
26.             if(arr[tmp2] < key)
27.             {
28.                 key = arr[tmp2];
29.                 keyin = tmp2;          
30.                 ch = 1;
31.             }
32.         }
33.         if(ch == 1)
34.         {
35.             arr[keyin] = arr[tmp];
36.             arr[tmp] = key;
37.         }
38.  
39.         ch = 0;
40.     }
41.  
42.     printf("후: ");
43.     for(dis = 0; dis<5;dis++)
44.     {
45.         printf("%d ",arr[dis]);
46.     }  
47.     printf("\n");
48.     return 0;
49. }

결과