알고리즘 - 퀵 정렬

- quick sort
 

- 분할 정복(divide and conquer) 방법, 보통 재귀를 이용하여 구현

- 합병 정렬과 달리 비균등하게 분할

- 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택하고 피벗을 기준으로 분할

- 속도가 빠르고 추가 메모리 공간을 필요로 하지 않음, 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 등에 기인

- 시간 복잡도 분석
 : 재귀 호출의 깊이는 
 : 각각의 패스에서 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어짐, 레코드의 이동 횟수는 비교 횟수보다 적으므로 무시
 : 총 시간 복잡도는 

- 단점으로
 : 정렬된 리스트에 대해서는 오히려 수행시간이  되버리는 불균형 분할 발생 -> 단순히 왼쪽 데이터를 피벗으로 사용하지 않고 리스트 내의 몇개의 데이터 중에서 크기순으로 중간 값(median)을 피벗으로 선택하여 극복 (왼쪽, 오른쪽, 중간의 3개의 데이터 중에서 크기순으로 중간값을 선택하는 방법(median of three)

- CODE

#include < iostream>
using namespace std;

int arr[1000001];

int partition(int *a, int low, int high) {
	int pivotIndex = low + (high - low) / 2;
	int pivotValue = arr[pivotIndex];
	swap(arr[pivotIndex], arr[high]);
	int pos = low;
	for (int i = low; i < high; i++) {
		if (a[i] < pivotValue) {
			swap(a[i], a[pos]);
			pos++;
		}
	}
	swap(arr[pos], arr[high]);
	
	return pos;
}

void quicksort(int *a, int low, int high){
	if (low < high) {
		int pivot = partition(a, low, high);
		quicksort(a, low, pivot - 1);
		quicksort(a, pivot + 1, high);
	}
}

int main()
{
	int n;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	quicksort(arr, 0, n - 1);

	for (int i = 0; i < n; i++) {
		cout << arr[i] << "\n";
	}

	return 0;
}