선택정렬 (Selection Sorting)

선택 정렬은 오름차순 기준으로 1회전 시 마다, 가장 작은 숫자를 선택하여 맨 앞으로 차례대로 정렬하는 기법이다.

입력 배열 외에는 다른 추가 메모리를 요구하지 않는, 즉 한 리스트안에서 교환해여 해결하는 것을 제자리 정렬(in-place sorting)이라고 한다.

1. 입력 배열에서 정렬되지 않은 값 중 최솟값을 검색

2. 이 최솟값을 배열의 1 번째 요소와 교환

3. 1 번째 요소(배열 중 최솟값, 정렬이 완료된 요소)를 제외한 나머지 값 중에서 가장 작은 값을 검색

4. 이 최솟값을 배열의 두 번째 요소와 교환

5. 이 과정을 배열요소갯수-1만큼 되풀이

주의할 점은, index값이 0에서 n-2까지만 변화된다.

만약 A[0]부터 A[n-2]까지 정렬되어 있다면 이미 A[n-1]이 가장 큰 값이기 때문에, n-1까지 계산할 필요가 없다.

예를 들어 요소의 갯수가 5개이고

3 2 6 1 5  라는 배열이 있다면

1스캔 - 1 2 6 3 5

2스캔 - 1 2 6 3 5

3스캔 - 1 2 3 6 5

4스캔 - 1 2 3 5 6

위와 같은 절차가 행해진다.

선택정렬의 코드는 다음과 같다.

#define SWAP(x, y, t) (t=x, x=y, y=t)
void selection_sort(int list[], int n) {
    int least, tmp;
    for (int i = 0; i < n - 1; i++) {
        least = i;
        for (int j = i + 1; j < n; j++) // 최솟값 탐색
        if (list[j] < list[least]) {
            least = j;
        }
        SWAP(list[i], list[least], tmp);
    }
}

전체 프로그램

MAX_SIZE개의 난수를 발생, 배열 list에 저장. 난수의 발생 범위는 0~MAX_SIZE-1까지이다.

정렬하기 전의 배열 상태와 각 회전수에 정렬된 배열 상태를 출력한다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>

#define MAX_SIZE 10
#define SWAP(x, y, t) (t=x, x=y, y=t)

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

    for (int i = 0; i < n - 1; i++) {
        least = i;
        for (int j = i + 1; j < n; j++) // 최솟값 탐색
            if (list[j] < list[least]) least = j;
        SWAP(list[i], list[least], tmp);
    
        printf("%d회 정렬 결과 : ", i+1);
        for (int k = 0; k < n; k++)
        printf("%d ", list[k]);
        printf("\n");
    }

}

void main() {
    int list[MAX_SIZE];
    int n = MAX_SIZE;

    printf("<선택정렬>\n정렬 이전 배열 : ");
    for (int i = 0; i < n; i++) {// 난수 생성 및 출력
        list[i] = rand() % n; // 난수 발생범위 0 ~ n
        printf("%d ", list[i]);
    }
    printf("\n");

    selection_sort(list, n); // 선택 정렬 호출

    printf("최종 정렬 결과 : ");
    for (int i = 0; i < n; i++) // 정렬 결과 출력
        printf("%d ", list[i]);
    printf("\n");
    system("pause");
}

<성능평가>

4만개의 크기를 주고 시간을 재는 코드는 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>

#define MAX_SIZE 40000
#define SWAP(x, y, t) (t=x, x=y, y=t)

void selection_sort(int list[], int n) {
    int least, tmp;
    
    clock_t start = clock(); // 시간재기 시작
    for (int i = 0; i < n - 1; i++) {
        least = i;
        for (int j = i + 1; j < n; j++) // 최솟값 탐색
            if (list[j] < list[least]) least = j;
        SWAP(list[i], list[least], tmp);
    }
    clock_t end = clock(); // 시간재기 끝
    
    double diff = (double)(end - start) / 1000;
    printf("선택정렬\n크기 : 40000개\n%.4lf초", diff);

}

void main() {
    int list[MAX_SIZE];
    int n = MAX_SIZE;
    
    for (int i = 0; i < n; i++) {// 난수 생성 및 출력
        list[i] = rand() % n; // 난수 발생범위 0 ~ n
    }
    
    selection_sort(list, n); // 선택 정렬 호출
    
    printf("\n");
    system("pause");
}

 

보다 정확한 알고리즘 시간을 재기 위해 미사여구를 제외하고 오직 sorting하는 로직 내외에만 타이머를 걸었다.

참고로 printf함수는 오버헤드가 엄청나기 때문에 4만개 과정을 전부 찍으면 어차피 보기도 어려울 뿐더러 정확한 시간을 재는 것은 불가능하다.

현실에서도 굉장히 오래 기다려야한다.

먼저 비교 횟수를 구하기 위해 두 개의 for문의 실행 횟수를 계산한다.

외부 루프는 n-1번, 내부 루프는 0에서 n-2까지 변하는 i에 대해 (n-1)-i번 반복된다.

키 값들의 비교가 내부 루프 안에서 이루어지므로, 전체 비교 횟수는 다음과 같다.

 

 

레코드 교환 횟수는 외부 루프의 실행 횟수와 같으며, 한 번 교환하기 위해 3번의 이동이 필요하므로 전체 이동 횟수는 3(n-1)이 된다.

선택 정렬의 장점은 자료 이동 횟수가 미리 결정된다는 것이다.

단점은 자료가 정렬된 경우에는 불필요하게 자기 자신과의 교환을 하게 된다. 따라서 이 문제를 개선하려면, 최소값이 자기 자신이면 자료 이동을 하지 않는다. 비교 연산을 1개가 이동 연산 3개보다 시간이 적게 걸리므로 효과적이다.

if (i != least)
    SWAP(list[i], list[least], tmp);

 

선택 정렬의 문제점은 안정성인데, 값이 같은 레코드가 있는 경우 상대적인 위치가 변경될 수 있다는 것이다.