퀵 소트(Quick Sort)

https://github.com/GimunLee/tech-refrigerator/raw/master/Algorithm/resources/quick-sort-001.gif

이름이 퀵소트지만 가장 빠른 정렬 방법은 아니다.

평균 시간복잡도는 O(N*logN) 이고 최악의 경우 시간복잡도는 O(N^2)

 

동작 원리:

특정 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한뒤에 배열을 나누는(분할)방법을 사용

여기서 특정 값을 pivot 값이라고 하는데 보통 첫 번째 원소를 pivot으로 설정하고 초기 시작을 한다.

 

동작을 풀어서 설명하면 

피벗값을 설정한다

-> 왼쪽에서 부터 피벗값 보다 큰 숫자를 찾고 오른쪽에서 부터 피봇값 보다 작은 수를 찾는다.

-> low <= high 일 경우 low와 high를 바꾸고 아닐경우 high 피봇값을 바꾼다 high와 피봇값을 바꾸는 이유는 외부의 while문 자체 조건을 보면 low <= high이다 반복문을 종료하기 전에 피봇값을 중간으로 바꿔으주는 것

-> 이렇게 하면 피벗값 기준으로 왼쪽에는 피봇값 보다 작은 값이 존재하고 오른쪽에는 피봇값보다 큰 값이 존재한다.(코드에서 while문 과정)

-> 그러면 피봇값을 기준으로 2분할 되는데 각각 똑같이 quick sort를 수행해 주면 된다.

 

코드 :

#include <iostream>
#include <math.h>
#include <time.h>
using namespace std;
int arr[20];
 
void quickSort(int start ,int end) {
	if (start >= end) return;
	int pivot = start; // pivot은 첫번째 원소로 지정
	int low = start + 1;
	int high = end;
	int tmp;
	while (low <= high) {
		while (arr[low] <= arr[pivot] && low <= end) low++;
		while (arr[high] >= arr[pivot] && high > start) high--;
 
		if (low <= high) {
			tmp = arr[low];
			arr[low] = arr[high];
			arr[high] = tmp;
		}
		else {
			tmp = arr[pivot];
			arr[pivot] = arr[high];
			arr[high] = tmp;
			
		}
		
	}
	quickSort(start, high - 1);
	quickSort(high + 1, end);
}
int main() {
 
	srand(time(0));
	int max = 0;
	for (int i = 0; i < 20; i++) {
		arr[i] = rand() % 1000;
		if (max < arr[i]) max = arr[i];
	}
	cout << "### Before Sorting ###" << endl;
	for (int i = 0; i < 20; i++) {
		cout << arr[i] << " ";
	}
 
	cout << endl;
	int size = sizeof(arr) / sizeof(int);
	quickSort(0, size);
	cout << "### After Sroting ###" << endl;
	for (int i = 0; i < 20; i++) {
		cout << arr[i] << " ";
	}
 
}