정렬 알고리즘 중 구현하기 편한 선택 정렬 알고리즘이 있다.
이 알고리즘은 n개의 인풋에 대하여 time complexity로 O(n^2)의 시간 복잡도를 가진다.
알고리즘의 개략적인 로직은 다음과 같다.
- n개의 input 배열에 대하여 do
- for ( i = 0; i< n -1; i++)
- for ( j = i; j<n; j++)
- find min value;
- swap(input[i], input[min_value]);
이렇게 총 n^2만큼의 for 루프를 돌게 되면 정렬은 완료되게 된다.
해당 로직은 오름차순 선택 정렬에 대한 로직이며, 내림차순 선택 정렬을 하고자 할 때에는 최대값을 찾고 swap해주게되면 된다.
코드는 다음과 같다.
#include <stdio.h> #define MAX_INPUT_SIZE 1000 int getInput(int *src); void printArray(int *src, int count); void sortArray(int *src, int count); int main() { int src[MAX_INPUT_SIZE]; int inputCount; inputCount = getInput(src); if (inputCount == 0) { fprintf(stderr, "Fatal Error: Input Error.\n"); return -1; } printf("Input source\n"); printArray(src, inputCount); sortArray(src, inputCount); printf("Output source\n"); printArray(src, inputCount); return 0; } int getInput(int *src) { int tmp; int count = 0; while (1) { printf("input integer (exit == -1) => "); scanf("%d", &tmp); if (tmp == -1) { return count; } else { src[count] = tmp; count++; } } } void printArray(int *src, int count) { int i; for (i = 0; i < count; i++) { printf("%d ", src[i]); } printf("\n"); } void sortArray(int *src, int count) { int i, j; int tmp_min, tmp_index = 0, tmp; for (i = 0; i < count - 1; i++) { tmp_min = src[i]; for (j = i; j < count; j++) { if (tmp_min >= src[j]) { tmp_min = src[j]; tmp_index = j; } } tmp = src[i]; src[i] = src[tmp_index]; src[tmp_index] = tmp; } }
코드의 실행 결과는 다음과 같다.