[백준] 2750번 - 퀵 정렬

#include <string>
#include <iostream>
#define SWAP(a,b) { int t;t=a;a=b;b=t; }
using namespace std;

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

	// 구간이 1이면 정렬 끝
	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]);             // 기준값과 i위치의 값 교환
	QuickSort(ar, left);                           // 왼쪽 구간 정렬
	QuickSort(ar + left + 1, num - left - 1);        // 오른쪽 구간 정렬
}

int main() {	
	int count;	
	cin >> count;
	int* nums = new int[count];
	for (int i = 0; i < count; i++) {
		int a;
		cin >> a;
		nums[i] = a;
	}	

	QuickSort(nums, count);

	for (int i = 0; i < count; i++) {
		cout << nums[i] << '\n';
	}
}

 

기준 값 key를 배열의 끝 요소로 정하고 left를 배열의 첫 요소, right을 배열의 끝에서 두번째 요소로 정한다.

그리고 left와 right이 중앙으로 이동하면서 left는 기준 값보다 큰 값, right은 기준 값보다 작은 값을 찾는다.

left 와 right을 반복하고 left가 right보다 커질 때 기준값과 left를 교환하면 기준값 앞에 있는 요소들은 기준 값보다 작은 값들, 뒤에 있는 요소들은 큰 값들로 정렬된다. 이것은 최초의 상태와 똑같으므로 기준 값 앞에 요소들과 뒤에 요소들에 대해서 재귀 호출로 정렬을 다시 실행한다.