선택 정렬

정렬

정렬(sorting)은 물건을 크기순으로 오름차순이나 내림차수능로 나열하는 것을 의미한다. 예를 들어 책들은 제목순이나 저자순, 또는 발간연도순으로 정렬이 가능하다. 사람도 나아가 키, 이름 등을 이용하여 정렬할 수 있다. 물건뿐만아니라 어떤 형태의 것도 서로 비교만 가능하다면 정렬할 수 있다.

정렬은 컴퓨터 공학에서 가장 기본적이고 중요한 알고리즘 중의 하나로 일상생활에서 많이 사용된다. 또한 정렬은 자료 탐색에 있어서 필수적이다. 예를 들면 사전에서 우리가 단어를 쉽게 찾을 수 있는 것은 사전안의 단어들이 알파벳순으로 정렬되어 있기 때문이다.

일반적으로 보통 정렬시켜야 될 대상은 레코드라고 불린다. 레코드는 다시 필드라고 하는 단위로 나누어진다. 예를 들어 학생들의 레코드라면 이름, 학번, 주소, 전화번호 등이 필드가 될 것이다. 여러 필드 중에서 특별히 레코드와 레코드를 ㅈ식별해주는 역할을 하는 필드를 키라고 한다.

선택 정렬

선택정렬은 가장 이해하기 쉬은 정렬 방법이다. 먼저 왼쪽 리스트와 오른쪽 리스트, 두 개의 리스트가 있다고 가정하자. 왼쪽 리스트에는 정렬이 완료된 숫자들이 들어가게 되며 오른쪽 이스트에는 정렬되지 않은 숫자들이 들어 있다. 선택정렬은 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 되풀이 한다. 선택정렬은 오른쪽 리스트가 공백상태가 될 때까지 이 과정을 되풀이하는 정렬 기법이다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x, y, t) ( (t) = (x), (x) = (y), (y) = (t) )

int list[MAX_SIZE]
int n;

void selection_sort(int list[], int n){
	int i, j, least, temp;
	for(i = 0; i < n - 1, i++){
		least = i;
		for(j = i + 1; j < n; j++) //최소값 탐색
			if(list[j] < list[least]) least = j;
		SWAP(list[i], list[least], temp);
	}
}

int main(void){
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for(i = 0; i < n; i++). // 난수 생성 및 출력
		list[i] = rand() % 100;  //난수 발생 범위 0 ~ 99

	selection_sort(list, n); // 선택정렬 호출
	for(i=0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

선택정렬의 분석

선택 정렬의 성능 분석을 위하여 비교 횟수와 이동 횟수를 따로 구하여 보자. 먼저 비교 횟수를 구하기 위하여 두개의 for 루프의 실행 횟수를 계산하여 보자. 외부루프 n-1번 실행될 것이며 내부루프는 0에서 n-2까지 변하는 i에 대하여 (n-1)-i번 반복될 것이다.

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

(n + 1) + (n + 2) + (n + 3) + (n + 4) … + 1 = n(n - 1) / 2 = O(n^2)

레코드 교환 횟수는 외부 루프의 실행 횟수와 같으며 한번 교환하기 위하여 3번의 이동이 필요하므로 전체 이동 횟수는 3(n - 1)이 된다. 선택 정렬의 장점은 자료 이동 횟수가 미리 결정된다는 점이다. 그러나 이동 횟수는 3(n - 1)으로 상당히 큰 편이다. 또란 자료가 정렬된 경우에는 불필요하게 자신 자신과의 이동을 하게 된다 따라서 이 문제를 약간 개선하려면 다음과 같은 if 문을 추가하면 된다.

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

즉 최소값이 자기 자신이면 자료이동을 하지 않는다. 일반적으로 비교 연산 1개가 이동 연상 3개보다 시간이 적게 걸리므로 효과적이다. 선택 정렬의 문제점은 안정성을 만족하지 않는다는 점이다. 즉 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.