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

#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++)
	{
		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[] = "student";
 
     printf("정렬 전의 문자열 : %s\n", str);
     SelectionSort(str, strlen(str));
     printf("정렬된 문자열 : %s\n", str);
}

프로그램 실행화면

선택정렬은 최소값을 찾아 앞쪽으로 이동하기를 배열의 크기만큼 반복하는 정렬 방법이다. 배열에서 제일 작은 값을 찾아 처음으로 일단 보낸다.

그리고 첫 번째 요소는 제외하고 남은 요소들 중 제일 작은 값을 다시 찾아 선두로 보내기를 배열 끝까지 반복한다.

작은 순서대로 계속 앞쪽으로 이동하므로 루프가 끝나면 모든 요소는 순서대로 정렬된다. 버블정렬과의 차이는 어떤게 있을까? 우선 반복문의 반복 횟수는 똑같아 보인다.

하지만 버블정렬보다 스왑하는 수는 훨씬 적다. 버블 정렬은 가장 큰 수가 앞에 있을 경우 이 큰 수가 제일 뒤로 갈때까지 swap하기 때문에 그만큼 메모리에 접근해 값을 변경 시키는 작업이 많은 것이다.

swap은 매크로로 구현해 보았다. 굳이 매크로로 할 필요는 없지만 간단한 코드 이기에 매크로로 해보았고 swap은 자주 사용될 수 있기 때문에 따로 만들어두면 더 좋을 것이다.