Quick Sort (D&C)접근

MergeSort와 다르게 Combine 단계를 없임

-> Divide의 단계가 중요해짐

pivot(기준점)을 잡고 divide 후 conquer(해결) 하면 된다.

#include<stdio.h>
#include<stdlib.h>

template <typename T>
void swap(T* a, T* b) {
	T tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

template <typename T>
int partition(T arr[], int low, int high) {
	T pivot = arr[high]; // 기준점
	int i = (low - 1); 

	for (int j = low; j < high; j++)
	{		
		if (arr[j] < pivot)
		{
			i++; 
			swap(&arr[i], &arr[j]);
		}
	}
	swap(&arr[i + 1], &arr[high]);
	return (i + 1);
}

template <typename T>
void quickSort(T arr[], int low, int high) {
	if (low < high) {
		int pi = partition(arr, low, high);

		quickSort(arr, low, pi - 1);
		quickSort(arr, pi + 1, high);
	}
}

 

TimeComplexity

T(n) = Divide + Conqer + Combine

      = (n-1) + T(n/2) + T(n/2) + 0   --> Best-case

      = 2T(n/2) + n

      = 2^k * T(n/2^k) + kn  (2^k=n)

      = O(nlogn)

---------------------------------------------------------------

      = (n-1) + T(n-1) + 0      --> Worst-case

      = T(n-2) + (n-2) + (n-1)

      = n(n-1)/2

      = O(n^2)