Selection Sort   선택 정렬

1. 선택 정렬 (Selection Sort)

  ㅇ 매 반복 패스 마다,
     - 가장 큰/가장 작은 자료를 선택(select)하고, 
     - (즉, 찾아서, 위치를 기억하고 있다가)
  ㅇ 해당 반복 패스가 끝날 때, 
     - 이를 맨앞/맨뒤로 옮기는(교환하는) 과정을 수행
     - (이 과정에서, 순서대로 정렬된, 리스트로써 나타남)
  ㅇ 전체 자료에 대해,
     - 이러한 과정을 반복적으로 수행


2. 선택 정렬의 특징

  ㅇ 키(Key)에 의해 이루어지고, 사실상 필요시에 만 교환 됨 

  ㅇ 제자리 정렬 (in-place sort)
     - 입력 배열 외에 추가적인 메모리가 불필요 
        . 단, 교환 동작 수행을 위한 임시 1개 필요  =>  O(1)
     - 입력 배열 그 자체를 사용하여 정렬시키고, 그 정렬된 배열을 그대로 반환

  ㅇ 안정적이지 못한 정렬 (nonstable sort)
     - 정렬 전 입력 자료 순서가 유지되지 못함

  ㅇ 기본 연산 둘 : 비교 연산, 교환 연산
     - 비교 필요 횟수 : 총 n(n-1)/2회의 데이터 비교가 필요함  =>  O(n2)
        . 설사 정렬되어 있더라도, 무조건 n(n-1)/2회의 데이터 비교가 필요함
        . 즉, (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 ≤ n2
     - 교환 필요 횟수 : 총 n-1 반복 패스 중 n-1번 교환 필요함  =>  O(n)

  ㅇ 시간복잡도 : O(n2)
     - 입력 데이터 상태가 어떻든지간에 언제나 동일한 수행 시간 O(n2)을 갖음

  ㅇ 데이터량이 적을때는, 비교적 좋은 성능을 보임


3. 선택 정렬의 방법

  ㅇ 2개의 중첩 루프를 사용
     - 외부 루프는, 남은 배열의 첫 요소부터 마지막까지 반복
        . 정렬 대상이 되는 배열의 크기를 하나씩 줄여주는 역할을 함
     - 내부 루프는, 해당 배열의 다음(나머지 첫) 요소부터 마지막까지 반복

  ㅇ 즉, 
     - 처음과 나머지 자료들과 비교하면서, 
     - 제일 큰/작은 자료를 맨 오른쪽/왼쪽에 두도록, 위치 교환
     - 직후 자료와 그 나머지 자료들과 비교,위치 교환을 반복해가며, 정렬해나감


4. 프로그래밍 例 (C 언어)

    
/* 선택정렬 (오름차순) */
Input  : (정렬 전 데이터 배열) A[], (배열 데이터 수) int n
Output : (정렬 후 데이터 배열) A[]

void SelectionSort(int A[], int n) {
    int outer, inner, min, temp;
    for (outer = 0; outer < n-1; outer++) {
        min = outer;
        for (inner = outer + 1; inner < n; inner++) {
            if (A[inner] < A[min]) {
               min = inner;
            }
        }
        // 교환 : A[outer] ↔ A[min]
        temp = A[min];
        A[min] = A[outer];
        A[outer] = temp;
    }
}