[Data Structure] Quick Sort 구현

첫번쨰 요소를 피벗으로 할때

#include <iostream>

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

int partition(int a[], int l, int h) {
	int pivot = a[l];
	int i = l, j = h;

	do {
		do { i++; } while (a[i] <= pivot);
		do { j--; } while (a[j] > pivot);

		if (i<j) {
			swap(a[i], a[j]);
		}
	} while (i < j);

	swap(a[l], a[j]);
	return j;
}

void QuickSort(int a[], int l, int h) {
	int pivot;
	if (l < h) {
		pivot = partition(a, l, h);
		QuickSort(a, l, pivot);
		QuickSort(a, pivot + 1, h);
	}
}

int main() {
	int a[] = { 10,50,70,20,90,30,INT32_MAX };
	int n = sizeof(a) / sizeof(a[0]);

	QuickSort(a, 0, n-1);

	for (int i = 0; i < n; i++) {
		std::cout << a[i] << " ";
	}

	return 0;
}