선택정렬 Selection Sort

이 첨부 파일에 있는 건 일반적인 함수의 형태이다. (int형 뿐 아니라 모든 형태의 자료형을 비교할 수 있도록 만든 것이다)
자료 배열의 선두 번지인 base,
자료의 개수 nelem,
레코드의 크기 width,
키값의 비교를 하는 함수 포인터 fcmp 를 뜻한다.
fcmp 함수는
int intcmp(const void *a, const void *b) 등을 뜻한다.


■ 선택 정렬 개념

실제 프로그래밍에 많이 사용되는 간단한 정렬 방법으로 첫번째 키 부터 기준키로 설정하며, 기준키로 설정된 값과 두번째 위치, 세 번째 위치, … n 번째위치의 값과 비교하면서 정렬
가장 작은 인자를 찾아서 제일 앞에 놓고, 이 다음 작은 인자를 찾아 앞에 놓는 방법을 반복
예 : 열 장의 명함을 놓고 이름을 가나다순으로 다시 정리하는 방법
    - 가장 먼저 오는 이름을 가진 명함을 찾아서 제일 앞에 놓음
    - 그 다음 올 수 있는 명함을 두 번째에 놓고... 하는 작업을 반복하여 열 개의 명함들을 정리
■ 선택 정렬 단계(오름차순의 경우)

입력 레코드에서 가장 작은 키 값을 갖는 레코드를 찾아 첫 번째 위치에 있는 레코드와 교환
첫 번째 위치한 레코드를 제외한 n-1개의 레코드중에서 가장 작은 키 값을 갖는 레코드를 찾아 두 번째 위치에 있는 레코드와 교환
이러한 수행 과정을 반복 수행하면 최종적으로 n-1번째 레코드와 n번째 레코드 중 키 값이 작은 레코드를 n-1번째에 위치시켜 정렬을 종료

■ 주어진 배열 A 가 n개의 데이터를 가질 때 선택정렬의 수행 단계

배열 A 에서 가장 작은 값을 갖는 데이터를 찾는다.
그 데이터를 배열의 맨 처음 데이터인 A[0]와 교환한다.
두 번째 작은 값을 갖는 데이터를 찾아서 배열의 두 번째 데이터인 A[1]과 교환한다.
배열의 전체 데이터가 정렬될 때까지 이 과정을 반복한다.



■ 선택 정렬 알고리즘

----------------------------------------------
void SelectionSort(int A[], int n)
{
    int i, j, min;
    for (i=0; i < n-1; i++)
    {
        min = i;
        for (j=i+1; j < n; j++)
            if (A[j] < A[min])  min = j;
        temp = A[min];
        A[min] = A[i];
        A[i] = temp;
    }
}
-----------------------------------------------


■ 성능

기본 연산 : 최소값을 갖는 데이터를 찾기 위한 비교연산과
                 필요하면 데이터들의 위치를 교환하여주는 교환연산
첫 번째 단계 : 주어진 n개의 데이터 중에서 최소값을 찾기 위하여 (n-1)번의 비교가 수행
두 번째 단계 : 나머지 (n-1)개의 데이터 중에서의 최소값을 찾기 위한 (n-2)번의 비교가 수행
선택정렬 알고리즘을 이용하여 n개의 데이터를 정렬하려면 약 n2/2 번의 비교를 수행
==> O(n2)
선택정렬 알고리즘에서는 매 단계마다 최대 한번씩의 교환이 일어나므로 전체적으로 볼 때
(n-1)번의 교환이 수행
선택정렬 알고리즘은 주어진 배열 안에서 데이터들의 이동을 최소화하려는 목적으로 만들어짐
데이터의 양이 적을 때 아주 좋은 성능을 나타냄