Selection Sort

정렬 알고리즘 중 구현하기 편한 선택 정렬 알고리즘이 있다.
이 알고리즘은 n개의 인풋에 대하여 time complexity로 O(n^2)의 시간 복잡도를 가진다.
알고리즘의 개략적인 로직은 다음과 같다.

1. n개의 input 배열에 대하여 do
2.     for ( i = 0; i< n -1; i++)
3.         for ( j = i; j<n; j++)
4.             find min value;
5.         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;
    }
}

코드의 실행 결과는 다음과 같다.