이번에는 반복 알고리즘일 이용하는 선택 정렬 알고리즘을 알아봅시다.
선택 정렬 알고리즘은 제일 큰 값을 찾아 맨 뒤의 요소와 교체하는 방법을 반복하여 전체를 정렬하는 알고리즘입니다. 물론 제일 작은 값을 찾아 맨 앞의 요소와 교체하는 방법을 반복할 수도 있습니다.
선택 정렬 알고리즘을 의사코드(pseudo code: 논리적인 수행 흐름을 이해할 수 있게 작성한 코드)는 다음과 같습니다.
알고리즘
선택 정렬(base:컬렉션,n:원소 개수,compare:비교 논리)
반복(i:=n; i>1 ; i:= i-1)
반복(max=0,j:=1; j<i ; j:=j+1)
조건(compare(base[max], base[j]) < 0)
max := j
temp: = base[i-1]
base[i-1] = base[max]
base[max] = temp
![선택 정렬](http://ehpub.dothome.co.kr/wp-content/uploads/2022/04/3.-선택-정렬.png)
점근식 계산
이번에는 선택 정렬 알고리즘 성능을 분석합시다.
선택 정렬의 내부 반복문의 수행 시간을 S(i)라고 가정할게요. 내부 반복문은 j가 i+1에서 n까지 순차적으로 증가하므로 비교를 n-i번 수행함을 알 수 있어요. 따라서 S(i)= n-i죠.
외부 반복문은 i가 0에서 n까지 순차적으로 증가하면서 내부 반복문을 수행하고 교환 1회합니다. 수행 시간을 T(n)이라 가정하면 T(n) = S(0)+1 + S(1)+1 +S(n-2)+1 … +S(n-1)+1 이죠.
따라서 T(n) = S(0)+1 + S(1)+1 +S(n-2)+1 … +S(n-1)+1 = n+1 + n + n-1 + …+1
따라서 T(n)= n(n+1)/2 이고 점근식 표기에서 높은 차수의 항만 남고 상수를 버리므로 O(n^2)라고 할 수 있습니다. 선택 정렬도 순차 정렬과 거품 정렬처럼 O(n^2)이네요.
하지만 교환하는 시간은 O(n)이라는 차이가 있어요. 물론 전체 성능에 미치는 영향은 아주 작아요.
소스 코드
//선택 정렬(Selection Sort) #include <stdio.h> #define SWAP(a,b) {int t; t = a; a=b; b=t;}//a와 b를 교환 void SelectionSort(int *base, int n); int main(void) { int arr[10] = { 9,4,3,10,5,8,7,6,2,1 }; SelectionSort(arr, 10); return 0; } void ViewArr(int *arr, int n); void SelectionSort(int *base, int n) { int i, j; int maxi; ViewArr(base, n);//현재 상태 출력 for (i = n; i>1; i--)//정렬할 범위를 축소해 나갑니다. { maxi = 0; for (j = 1; j<i; j++) { if (base[maxi]<base[j])//더 큰 원소를 만나면 { maxi = j; } } SWAP(base[maxi], base[i - 1]);//교환 ViewArr(base, n);//상태 출력 } } void ViewArr(int *arr, int n) { int i = 0; for (i = 0; i<n; i++) { printf("%2d ", arr[i]); } printf("\n"); }
//https://ehpub.co.kr //[언제나 C언어] 선택 정렬(Selection Sort) [예제 Center] #include #include #include #pragma warning(disable:4996) #define LENGTH(arr) (sizeof(arr)/sizeof(arr[0])) #define SWAP(i, j) {int t; t=i; i=j; j=t;} #include //Sleep enum Color { LACK, BLUE, GREEN, JADE, RED, PURPLE, YELLOW, WHITE, GRAY, LIGHT_BLUE, LIGHT_GREEN, LIGHT_JADE, LIGHT_RED, LIGHT_PURPLE, LIGHT_YELLOW, LIGHT_WHITE }; void changecolor(int color) { SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color); } void View2(int *base, int n,int i, int j, int max,int r) { int s = 0; for (s = 0; s < n; s++) { if (s < j) { if (s == max) { changecolor(YELLOW); } else { changecolor(WHITE); } } else if (s == j) { changecolor(GREEN); } else if (s < i) { changecolor(WHITE); } else if (s >= i) { changecolor(PURPLE); } printf("%2d ", base[s]); } changecolor(WHITE); if (r) { printf("SWAP %d %d", base[i - 1], base[max]); } printf("\n"); } void SelectionSort2(int *base, int n)//선택 정렬(base:컬렉션, n : 원소 개수) { int max, j; for (int i = n; i > 1; i--) //반복(i: = n; i > 1; i: = i - 1) { for (max = 0, j = 1; j < i; j++)//반복(max = 0, j: = 1; j < i; j: = j + 1) { if (base[max] < base[j])//조건(base[max]< base[j]) { max = j;//max: = j } View2(base, n, i, j, max, 0); Sleep(1000); } SWAP(base[i - 1], base[max]);//교환(base[i-1],base[max]) View2(base, n, i, j, max, 1); } } void View(int *base, int n, const char *msg) { for (int i = 0; i < n; i++) { printf("%2d ", base[i]); } printf("%s\n", msg); } void SelectionSort(int *base, int n)//선택 정렬(base:컬렉션, n : 원소 개수) { int max, j; for (int i = n; i > 1; i--) //반복(i: = n; i > 1; i: = i - 1) { for (max = 0, j = 1; j < i; j++)//반복(max = 0, j: = 1; j < i; j: = j + 1) { if (base[max] < base[j])//조건(base[max]< base[j]) { max = j;//max: = j } } SWAP(base[i - 1], base[max]);//교환(base[i-1],base[max]) } } int main() { int arr[10] = { 9,4,3,0,5,8,7,6,2,1 }; View(arr, LENGTH(arr),"before"); getch(); SelectionSort2(arr, LENGTH(arr)); View(arr, LENGTH(arr),"after"); system("pause"); return 0; }