20-2-나.선택 정렬

가장 단순한 정렬 방법인 선택 정렬은 최소값을 찾아 앞쪽으로 이동하기를 배열 크기만큼 반복하는 정렬 방법이다. 배열에서 제일 작은 값을 찾아 처음으로 일단 보낸다. 그리고 첫 번째 요소는 제외하고 남은 요소들 중 제일 작은 값을 다시 찾아 선두로 보내기를 배열 끝까지 반복한다. 작은 순서대로 계속 앞쪽으로 이동하므로 루프가 끝나면 모든 요소는 순서대로 정렬된다.

선택 정렬은 사람이 정렬을 하는 상식적인 방법과 일치하는 쉬운 알고리즘이다. 선생님이 학생들을 키순으로 정렬할 때 사용하는 방법이 바로 선택 정렬이다. 선생님은 무작위로 늘어선 학생들 중 가장 작은 학생을 골라 이 학생을 줄 처음에 세운다. 그리고 남은 학생들 중 제일 작은 학생을 찾아 그 뒤에 세우기를 모든 학생에 대해 반복하는 것이다. 예제를 보자.

예 제 : SelectionSort

#include <Turboc.h>

#define SWAP(a,b) { int t;t=a;a=b;b=t; }

void SelectionSort(char *ar, int num)

{

int minidx;

int i,j;

// 배열 전체 순회.

for (i=0;i<num-1;i++) {

// i이후의 최소값을 찾는다.

for (minidx=i,j=i+1;j<num;j++) {

if (ar[minidx] > ar[j]) {

minidx=j;

}

}

// 최소값을 현재항과 교환.

if (minidx != i) {

SWAP(ar[minidx],ar[i]);

}

}

}

void main()

{

char str[]="winapi";

printf("정렬 전의 문자열 : %s\n",str);

SelectionSort(str,strlen(str));

printf("정렬된 문자열 : %s\n",str);

}

버블 정렬과 똑같은 문자열을 사용했으므로 실행 결과도 동일하다. 역시 이중 루프로 구성되어 있는데 선택 정렬의 단계별 동작을 그림으로 그려 보면 다음과 같다.

i가 0일 때 j는 i의 다음 위치에서부터 배열의 끝까지 순회하면서 가장 작은 값을 가지는 요소의 첨자를 minidx에 선택하는데 첫 번째 그림에서 가장 작은 값은 a이다. 이렇게 선택된 a와 첫 번째 요소 w의 값을 교환하면 a는 이미 제 위치를 찾았다. i의 다음 루프에서는 1번째 자리에 위치시킬 가장 작은 값을 다시 선택하는데 이때는 1번째 자리에 이미 배치되어 있는 i보다 더 작은 값이 없으므로 교환이 발생하지 않는다.

다음 i 루프에서 그 다음 작은 값 i를 n과 교환하고 다음 루프에서 w와 n이 교환된다. 마지막 남은 w는 더 이상 교환할 대상이 없으므로 이 시점에서 정렬을 종료한다. 이런 식으로 루프를 끝까지 돌면 작은 값들이 순서대로 앞쪽으로 이동하면서 정렬된다. 뒤쪽의 미정렬된 레코드에서 가장 작은 값을 선택해서 앞쪽으로 이동시키기 때문에 선택 정렬이라고 한다. 루프를 거꾸로 돌면서 큰 값을 찾아 뒤쪽으로 보내는 방법을 써도 동일하다.

선택 정렬은 작은 값을 선택하기 위해 비교를 여러 번 하지만 교환 회수가 작은 것이 장점이다. 최악의 경우라고 하더라도 레코드의 개수만큼만 교환이 발생하므로 교환 비용이 비싼 구조체 배열 등에 적합하다. 선택 정렬은 가장 작은값과 현재값을 교환하는 방식이라 현재값이 뒤쪽의 어디로 갈 지 알수 없으므로 안정성은 없다.