[C언어 알고리즘] 정렬(2) - 선택정렬 (Selection sort)

선택정렬은 가장 간단한 정렬 알고리즘입니다. 실생활 속에서 가장 많이 사용하는 예를 들자면, 카드패 정렬입니다, 카드 뭉치에서 가장 작은 숫자 카드를 맨앞에 놓고 그 다음 작은 숫자카드를 놓고 ...의 작업을 반복하여 정렬하는 방법을 선택정렬 이라고 합니다.

 

선택정렬 알고리즘

이번 포스팅에서는 문자형 배열을 정렬하는 것으로 해보겠습니다. 
의사코드(Pseudo code)를 적어보면 다음과 같습니다.

1. i =0 
2. i 가 n-2 이면 끝난다. 
  2-1. 배열의 i항 부터 n-1항까지 중 최솟값을 찾아 min에 저장한다. 
  2-2. 배열의 i항과 min항을 교환한다. 
  2-3. i를 1 증가시키고 2로 돌아간다.

다음과 같은 문자형 배열이 있다고 가정해 봅시다.

첫 번째 수행은 아래와 같습니다.

첫 번째 수행 전

가장 먼저 첫번째 요소인 's'부터 데이터 중 가장 작은 값인 'c'를 찾아서 서로 값을 교환하면 아래와 같은 결과를 얻습니다.

첫 번째 수행 후

 

두 번째 수행은 다음과 같습니다.

두 번째 수행 전

두 번째 수행 후

두 번째 수행에서는 두번째 요소인 'e'에서 시작하여 가장 작은 값을 찾아내어 각 요소를 바꾸는데 같은 'e'가 가장 작은 값이라 내용에 변화는 없어 보입니다.

 

세 번째 수행은 다음과 같습니다.

세 번째 수행 전

세 번째 수행 후

세번째 수행은 세번째 요소인 'l'에서 시작하여 가장 작은 값인 'e'를 찾아 각 요소를 교환합니다.

 

이런 식으로 n-2번째 요소까지 수행하면 정렬이 끝납니다.

 

아래는 선택정렬을 구현한 소스입니다.

#include <stdio.h>
#include <string.h>

void print_data(char a[], int n);

void selection_sort(char a[], int n)
{
    char min;					/* 최솟값을 저장 */
    int minindex;				/* 최솟값의 인덱스 저장 */
    int i, j;

    for (i = 0; i < n-1; i++) {
        minindex = i;				/* 각 단계별 수행 시작 설정 */
        min = a[i];
        for (j = i+1; j < n; j++) {		/* 각 단계별 요소 이후로 최솟 값을 찾기 */
            if (min > a[j]) {			/* 더 작은 값이 존재할 경우 바꾸기 */
                min = a[j];
                minindex = j;
            }

        }
        a[minindex] = a[i];			/* 각 단계별 요소와 최솟값을 교환 */
        a[i] = min;
        print_data(a, n);			/* 교환된 결과를 프린트 */
    }
}

void print_data(char a[], int n) 
{
    int i;
    for (i = 0; i < n; i++) {
        printf ("%c ", a[i]);
    }
    printf ("\n");
}

void main (int argc, char *argv[])
{
    char data[] = "selectionsort";
    print_data(data, strlen(data));		/* 정렬 시작 전 데이터 프린트 */
    selection_sort(data, strlen(data));		/* 선택정렬 수행 */
}

실행결과는 아래와 같습니다. 데이터가 13개이므로 첫 번째 줄을 제외하고 12번 수행이 되었는데 같은 문자가 많아

8번째 수행쯤에 이미 정렬이 다 되었지만 끝까지 수행을 했네요.

PS C:\CS> .\selection_sort.exe
s e l e c t i o n s o r t 
c e l e s t i o n s o r t
c e l e s t i o n s o r t
c e e l s t i o n s o r t
c e e i s t l o n s o r t
c e e i l t s o n s o r t
c e e i l n s o t s o r t
c e e i l n o s t s o r t
c e e i l n o o t s s r t
c e e i l n o o r s s t t
c e e i l n o o r s s t t
c e e i l n o o r s s t t
c e e i l n o o r s s t t

참 쉽죠~ 지금까지 선택정렬(Selection sort)이었습니다.