[C언어] 퀵정렬 알고리즘(quick sort)

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

void QuickSort(char *ar, int num)
{
	int left, right;
	char key;

	if(num <= 1) return;

	key = ar[num - 1];
	for(left = 0, right = num - 2; ; left++, right--)
	{
		while(ar[left] < key) left++;
		while(ar[right] > key) right--;
		if(left >= right) break;
		SWAP(ar[left], ar[right]);
	}
	SWAP(ar[left], ar[num - 1]);
	QuickSort(ar, left);
	QuickSort(ar + left + 1, num - left - 1);
}
 
void main()
{
     char str[]="greathuman";
 
     printf("정렬 전의 문자열 : %s\n", str);
     QuickSort(str, strlen(str));
     printf("정렬된 문자열 : %s\n", str);
}

프로그램 실행화면

퀵 정렬(Quick Sort)은 이름 그대로 속도가 대단히 빠른 정렬 알고리즘이다. 큰 배열을 일정한 기준값을 경계로 하여 기준값보다 큰 값들과 작은 값들로 구성된 작은 두 개의 배열로 분할한다.

그리고 분할된 각 배열을 똑같은 방법으로 다시 정렬하는 점진적인 방법을 사용한다. "greatehuman"이라는 문자열을 퀵 정렬하면 "aaeghmnrtu"가 된다.

큰 배열을 분할하기 위해 먼저 기준값을 선정하는데 배열 선두나 마지막을 기준값으로 사용하는 것이 가장 쉽다.

그리고 for 루프에서 배열의 왼쪽과 오른쪽에 각각 left, right 포인터를 두고 중앙으로 이동하면서 left에 기준값보다 큰 값, right에 기준값보다 작은 값을 찾는다.

그리고 두 값을 교환하여 기준값보다 작은 값은 배열의 왼쪽으로 보내고 큰 값은 오른쪽으로 보낸다. 이 과정을 left와 right가 만날 때까지 반복하는데 이때 left 는 기준값보다 큰 값을 가리킨다.

left와 기준값을 교환하여 left가 가리키는 값을 배열 끝으로 보내면 기준값의 왼쪽에는 이 값보다 작은 값만 있고 오른쪽에는 더 큰 값만 있을 것이다.

기준값이 있는 위치의 왼쪽 구간과 오른쪽 구간을 똑같은 방법으로 정렬하되 구간 크기가 1이 될 때까지 이 과정을 반복하면 전체 배열이 정렬된다.

참조 사이트