Selection Sort ( 선택 정렬 )

오름차순을 기준으로 정렬한다.

## 개념 요약 ##

• 제자리 정렬(in-place sorting) 알고리즘 중의 하나.

> 입력배열 (입력받은 배열값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법.

• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘.

> Ex) 첫 번째 순서에는 가장 최소값을 넣고, 2번째 순서에는 2번째 위치에 남은 값 중에서의 최소값을 넣고....

• 과정 설명

1) 주어진 배열 중에서 최소값을 찾는다.

2) 그 값을 맨 앞에 위치한 값과 교체한다. 

3) 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체.

4) 하나의 원소만 남을 때 까지 위의 1~3 과정을 반복.

## 구체적 개념 ##

- 선택정렬은, 첫 번째 값을 두번째 값부터 마지막 값까지 차례대로 비교하여 가장 작은 값을 찾아, 첫번째에 놓고, 2번째 자료를 세번째 부터 마지막 까지 비교해 그 중 작은 값을 찾아 2번째 위치에 놓는 과정을 반복하며 정렬을 수행한다!

- 1회전을 수행하고 나면, 가장 작은 값의 자료가 맨 앞에 오게 되므로, 그 다음 회전에서는 2번째 값을 가지고 비교한다. 

## Selection sort 의 특징 ##

장점 : 자료 이동 횟수가 미리 결정된다.

단점 : 안정성을 만족하지 않는다. 즉, 값이 같은 레코드가 있는 경우에는 상대적인 위치가 변경 될 수 있다.

## 시간 복잡도 ##

• 비교 횟수

> 2개의 for loop 의 실행 횟수.

> 외부 루프 : (n-1)번 

> 내부 루프 (최소값 찾기) : n-1, n-2, ... , 2, 1 번 

• 교환 횟수

> 외부 루프의 실행 횟수와 동일. 즉, 상수 시간 작업.

> 한번 교환하기 위하여 3번의 이동(swap 함수의 작업)이 필요하므로 3(n-1)번. ! 

• T(n) = (n-1) + (n-2) + .... + 2 + 1 = n(n-1)/2 = O(n^2)

## Sort Algorithm time complexity ##

• 단순 (구현이 간단) 하지만, 비효율적인 방법 

        > 삽입 정렬, 선택 정렬, 버블 정렬

• 복잡하지만, 효율적인 방법

        > 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

 

소스코드 ~ 

#include <stdio.h>
#define MAX_SIZE 5
#define SWAP(x, y, tmp) ( (tmp)=(x), (x)=(y), (y)=(tmp) )


void selection_sort(int list[], int n) {
    int i, j, least, tmp;

    for(i = 0; i < n-1; i++) {
        least = i;
        for(j = i+1; j < n; j++) {
            if(list[j]< list[least])
                least = j;
        }
        if(least != i) {
            SWAP(list[i], list[least], tmp);
        }
        for( int k = 0; k < MAX_SIZE; k++ )
            printf("%d ", list[k]);
        printf("\n");
    }

}

void main() {
    int i;
    int n = MAX_SIZE;
    int list[5] = {9,6,7,3,5};

    selection_sort(list, n);
    for(i = 0; i < n; i++) {
        printf("%d\n", list[i]);
    }
}