[CS] 퀵 정렬 (Quick Sort)

학부 1학년 때 컴퓨터 개론 시간에 C를 배웠던 것 같다. 당시 전혀 학과 공부를 신경쓰지 않던 나는 수업을 통해 배우는 게 별로 없었다. 아직도 C조차 제대로 모르는 이유는 여기에서 기인한다. 어쨌든, 그 때 마지막 과제던가? 퀵 정렬을 C로 짜오라는 과제가 있었던 것 같다. 당시에 퀵 정렬이라하면 최고 수준의 프로그래밍 실력이 있어야 할 수 있다고 생각했다. 마치, 1학년 당시 '학점이 3.0을 넘는 사람은 인간이 아니다'라고 믿었던 것처럼 어이없는 믿음이였지만 말이다. 재귀(recursion)가 들어가면 일단 머리가 돌아가지 않았다. 

 퀵 정렬의 기본 개념을 보면, 주어진 수 중에 임의의 값(pivot)을 기준으로 그 값보다 작은 값과 큰 값으로 나눈 후 이 pivot 값을 가운데 놓은 후, 두 부분을 각각 다시 퀵 정렬한다. 머지 정렬(merge sort)와 비슷한데, 머지 정렬은 단수히 두 분으로 계속 나누다가 합쳐질 때 양쪽에서 작은 값들 부터 뽑아 내어 정렬한다. A={1,3,4}와 B={2,5,9}가 있으면 A,B,A,A,B,B 순으로 앞의 수를 뽑아 {1,2,3,4,5,9}로 만들어 준다. 둘 다 평균 O(nlgn)의 시간 복잡도를 가진다. T(n)=T(n/2)+O(n)을 풀어서 나오는 듯.

#include <iostream>

using namespace std;

void swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void quicksort(int *arr, int s, int e) {
	int p = s;

	if (s >= e) return;	

	for (int i = s; i < e; i++) {
		if (arr[e] >= arr[i]) {
			swap(arr[i], arr[p]);
			p++;
		}
	}
	swap(arr[p], arr[e]);

	quicksort(arr, s, p-1);
	quicksort(arr, p+1, e);	
}

int main() {
	int arr[] = {8,1,3,7,4,15,9,11};
	int arr2[] = {9,4,1,3,24124,12412,412,412, 3,1};

	quicksort(arr, 0, 7);

	for (int i = 0; i < 8; i++)
		cout << arr[i] << " ";
	cout << endl;

	quicksort(arr2, 0, 9);

	for (int i = 0; i < 10; i++)
		cout << arr2[i] << " ";
	cout << endl;
}

학부 1학년으로 돌아가면 즐겁게 다시 공부할 수 있을 것 같다. ㅎㅎ