[알고리즘] 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

선택 정렬은 매 차례마다 순차적으로 각 인덱스에 해당하는 원소의 값(최소값or 최댓값)을 찾고 해당 인덱스의 원소와 교환해주는 정렬입니다.

매 차례마다 남은 원소들을 모두 확인해야 하기 때문에 알고리즘 상 시간 복잡도는 최악의 연산 횟수나 평균 연산 횟수나 O(N^2) 입니다.

그림

크기가 5인, 배열을 예로 그림을 통해 설명하겠습니다. 

순차적으로 각 인덱스마다(5단계) 해당하는 원소의 값(최소값)을 찾고 해당 인덱스(각 단계)에서 원소를 교환해주는 방법입니다. 

1단계에서 첫 번째 인덱스의 값은 '19'를 가리키고, 이후 인덱스에서 최소값 '6'을 찾아서 교환합니다. 

2단계에서 두 번째 인덱스는 '89'를 가리키고, 첫 번째 인덱스(이미 정렬이 된)를 제외한 인덱스에서 최소값 '9'를 찾아서 교환합니다. 

3단계에서도 위와 마찬가지로 구현하고 N단계까지 수행을 완료하면 크기 N개의 배열에 대해 정렬이 됩니다.

의사코드

위 연산 과정의 의사코드는 다음과 같습니다.

selectionSort{
    ary[SIZE]
    for i = 1 to SIZE{
        idx = i
        for j = i+1 to SIZE{
            if ary[j] > ary[idx]
                idx = j
        }
        swap( ary[idx], ary[j] )
    }
}

예제

선택 정렬을 사용한 예제 코드는 아래와 같습니다.

- 입력

첫 줄에 정렬할 원소의 수 N

둘째 줄부터 정렬할 원소 N개의 정수

- 출력

선택정렬 후 정렬된 원소 결과 출력

-코드

#include <stdio.h>
 
#define SIZE 100
 
#define SWAP(a, b, type) do { \
    type tmp;    \
    tmp = a;    \
    a    = b;    \
    b    = tmp;    \
}while (0)
 
void selectionSort(int ary[], int N) {
    // 배열의 자료형(ary)과 배열의 크기(N)를 
    // 입력받고 선택 정렬을 수행하는 함수 
    int i;
    int j;
    int idx; 
 
    for (i = 0; i < N-1; i++) {
        idx = i;
        for (j = i + 1; j < N; j++) {
            if (ary[j] < ary[idx]) {
                idx = j;
            }
        }
        SWAP(ary[idx], ary[i], int);
    }
}
void printAry(int ary[], int N) {
    // 배열의 자료형(ary)과 배열의 크기(N)를 
    // 입력받고 배열의 원소를 출력하는 함수 
    int i;
 
    for (i = 0; i < N; i++) {
        printf("%d ", ary[i]);
    }
    printf("\n");
}
int main(void) {
    int ary[SIZE];
    int i;
    int N;
 
    // 배열의 크기를 표준입력으로부터 입력
    scanf("%d", &N);
 
    // 배열의 크기 만큼 반복문을 통해 배열의 원소를 초기화
    for (i = 0; i < N; i++) {
        scanf("%d", &ary[i]);
    }
 
    // 선택 정렬 함수를 호출하고 배열의 원소를 출력
    selectionSort(ary, N);
    printAry(ary, N);
    //fflush(stdout);
    getchar();
    getchar();
 
    return 0;
}