Quick Sort 정의, 알고리즘 및 코드에 대해

Quick Sort란, Divide And Conquer 방식을 사용하는 정렬 알고리즘이다

Merge Sort와 함께 많이 쓰이면서, 시간 복잡도가 O(nlog n)으로 실용적이고 빠르다 🤗

 

1️⃣ Array의 Size가 1이면 해당 Array를 return

2️⃣ Size가 2 이상이면 pivot element를 하나 정한다

3️⃣ A1을 Array에서 pivot보다 작은 element, A2를 Array에서 pivot과 크기가 같은 element, A3를 A에서 pivot보다 큰 element를 담은 Array로 Divide한다

4️⃣ A1, A2, A3를 Quick Sort한 다음 return된 A1, A2, A3 순서대로 이어 붙인다(Conquer and Merge)

 

array의 0번째 index를 pivot으로 설정할 경우

위와 같이 Divide 해준 뒤, 회색으로 칠해진 element들을 순서대로 merge하면 sorting된 Array를 얻을 수 있다 !

점화식은 T(n) = 3T(n/3) + O(n)으로 구할 수 있고, 이 때 시간 복잡도는 O(nlog n)이다

 

하지만 pivot을 맨 앞의 원소로 정하는 과정에서 array가 decreasing하게 sorted 되어있다면?

ex) 8,7,6,5,4,3,2,1

array를 divide할 때 마다 element가 A1으로 몰리게 되고, 최악의 경우 n번의 quick sort 함수를 호출해야 한다!!

따라서 Worst-case에서는 O(n^2)의 시간복잡도를 가진다

그에 반해 pivot이 언제나 중간값인 median을 선택할 경우, T(n) = 2T(n/2) + O(n)의 점화식을 얻을 수 있다

따라서, Best-case에서의 시간복잡도 또한 O(nlog n)이다

 

평균적인 퀵소트의 시간복잡도는 O(nlog n)로 알려져있다

#include <cstdio>
#include <cstdlib>
void quickSort(int* A, int min, int max) {
	int size = max - min + 1;
	int c_a1, c_a2, c_a3, pivot, i;
	if (size <= 1)return;
	
	pivot = A[min];
	int* A1 = (int*)malloc(sizeof(int) * size);
	int* A2 = (int*)malloc(sizeof(int) * size);
	int* A3 = (int*)malloc(sizeof(int) * size);
	c_a1 = 0;
	c_a2 = 0;
	c_a3 = 0;
	for (int i = min; i <= max; i++) {
		if (A[i] < pivot) {
			A1[c_a1] = A[i];
			c_a1++;
		}else if(A[i]==pivot) {
			A2[c_a2] = A[i];
			c_a2++;
		}
		else {
			A3[c_a3] = A[i];
			c_a3++;
		}
	}
	quickSort(A1, 0, c_a1 - 1);
	quickSort(A3, 0, c_a3 - 1);
	for (i = 0; i < c_a1; i++) A[min + i] = A1[i];
	for (i = c_a1; i < c_a1 + c_a2; i++) A[min + i] = A2[i - c_a1];
	for (i = c_a1 + c_a2; i < size; i++) A[min + i] = A3[i - (c_a1 + c_a2)];
}
int main() {
	int size = 7;
	int A[7] = { 3,7,2,8,6,5,9 };
	int i = 0;
	quickSort(A, 0, size - 1);
	for (int i = 0; i < size; i++)
		printf("%d ", A[i]);
	return 0;
}