첫째는 SelectionSort, 선택 정렬이다.
원리
1. 0부터 끝요소까지 반복한다.( current < N )
2. 현재요소( current )와 나머지 요소 중 가장 작은 값을 비교하여 더 작다면 교환이 일어난다.
특징
1. 가장 작은 값을 찾는 과정에서 비교는 여러번 일어나지만 실제로 교환은 한번만 일어 나므로 범위가 작을경우 유리하다.
2. 데이터양이 큰 경우 매번 작은 값을 찾기 때문에 매우 느리다.
연산시간
1. 최선의 경우 비교횟수 : N - 1 ( 정렬이 이미 되어 있는 경우 )
2. 최악의 경우 비교횟수 :N * (N - 1) / 2 ( 역순으로 정렬되어 있는 경우 )
- 처음에는 가장 작은 값을 찾기위해 (N - 1) 번 비교할 것이며 하나씩 정렬 될 때마다 -1 씩 하여 끝에는 1번 비교하게 될 것이다.
즉, 비교횟수는 [ (N - 1) + (N - 2) + (N - 3) ... 1 ]이다.
식으로 나타내면 
= n(n-1) / 2 이며 O표기법으로는 O(n^2)이 된다.
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | //SELECTIONSORT void SelectionSort(int* array, int size) { for (int i = 0; i < size; i++) // i == (0 ~ size) { for (int j = i; j < size; j++){ // j == (i ~ size) if (array[i] > array[j]) // (i) > (j) 이면 교환 { int temp = array[i]; array[i] = array[j]; array[j] = temp; } } } } int const MAX = 5; // Max 값 int g_arr[MAX] = { 0, }; // 배열 초기화 int main() { printf("========정렬전========\n"); //AscendingNumber(g_arr, MAX); // 순열 배열 생성 //DescendingNumber(g_arr, MAX); // 역순 배열 생성 RandomNumber(g_arr, MAX); // 랜덤 배열 생성 PrintNumber(g_arr, MAX); // 배열 출력 printf("\n"); clock_t start = clock(); // 시작 시간 SelectionSort(g_arr, MAX); // SelectionSort clock_t end = clock(); // 끝 시간 printf("========정렬후========\n"); PrintNumber(g_arr, MAX); // 배열 출력 printf("\nTime : %f\n", ((double)(end - start)) / CLOCKS_PER_SEC); } | cs |
결과
시간
시간은 MAX 값 100,000 을 기준으로 측정하였다.
랜덤 배열 : 31.60
역순 배열 : 19.13
순열 배열 : 13.20
결론
선택정렬은 가장 직관적인 정렬인것 같다. (최소값을 앞에 정렬하는 것이기 때문)
또 10000개 이하 개수에 대해서는 비교하는 것에 비해 교환횟수가 적기 때문에 빠른 속도를 나타낸다.(10000개 기준 0.64초)
하지만 O(n^2)의 알고리즘 답게 요소가 많아질 수록 응답 시간이 길어지는 것이 확실히 보인다.
'All > Algorithm' 카테고리의 다른 글
| InsertionSort (0) | 2016.01.03 |
|---|---|
| BubbleSort (0) | 2016.01.02 |
| Sort Algorithm (0) | 2015.12.28 |
| JUMPGAME_알고리즘 (0) | 2015.12.28 |
| JUMPGAME_문제 (0) | 2015.12.28 |
