[Sorting] Chapter 03. 퀵 정렬

GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/2260b9e13b4c3da9221ca71a6b6d7a1515995208

퀵 정렬 · developeSHG/Data_Structure-Algorithm@2260b9e

 

 

---

 

 

퀵 정렬은 병합 정렬과 마찬가지로, 데이터를 둘 씩 쪼개서 진행하는 것은 비슷하다.

근데 병합 정렬은 시작부터 반으로 쪼갠 다음, 왼쪽 그룹과 오른쪽 그룹을 따로 정렬해서 정렬된 양 쪽 그룹을 합치는 형태로 조립했었다.

하지만 퀵 정렬은 처음부터 분할하기 보다는 어느정도 특정 알고리즘을 적용시켜 추출한 다음에, 왼쪽 그룹과 오른쪽 그룹을 나누는 형태가 된다.

 

---

 

퀵 정렬은 pivot이라는 기준 값이 있고, 이것을 토대로 정렬을 진행한다.

 

1단계)

- pivot >= arr[low]일 동안 low를 오른쪽으로 이동

- pivot <= arr[high]일 동안 high를 왼쪽으로 이동

 

2단계)

- low < high라면, arr[low]와 arr[high] 데이터 교체

Swap

 

다시 1단계와 2단계를 반복해서 실행한다.

 

그렇게 진행하다가 필연적으로 high와 low의 위치가 거꾸로 위치한 현상이 발생하게 된다. 그럼 이후엔 알고리즘을 진행하지 않고, 빠져나오면서 3단계를 진행한다.

 

3단계)

- high <= low면 빠져나오고, pivot과 arr[high] 교체

 

결과)

- pivot인 5의 위치는 확정됨.

- pivot(5)의 기준으로 왼쪽에는 더 작은 숫자, 오른쪽에는 더 큰 숫자가 밀집되어있다.

 

자리를 찾은 숫자를 제외하고, 나머지 부분을 재귀적으로 QuickSort

 

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;
#include <thread>
// 오늘의 주제 : 정렬

// [5][1][3][7][9][2][4][6][8]
// p
//           high low		  

int Partition(vector<int>& v, int left, int right)
{
	int pivot = v[left];
	int low = left + 1;
	int high = right;

	// O(N)
	while (low <= high)
	{
		while (low <= right && pivot >= v[low])
			low++;

		while (high >= left + 1 && pivot <= v[high])
			high--;

		if (low < high)
			swap(v[low], v[high]);
	}

	swap(v[left], v[high]);
	return high;
}

// O(N^2) < 최악
// O(NlogN) < 평균
void QuickSort(vector<int>& v, int left, int right)
{
	if (left > right)
		return;

	int pivot = Partition(v, left, right);
	QuickSort(v, left, pivot - 1);
	QuickSort(v, pivot + 1, right);
}

int main()
{
	vector<int> v;

	srand(time(0));

	for (int i = 0; i < 50; i++)
	{
		int randValue = rand() % 100;
		v.push_back(randValue);
	}

	QuickSort(v, 0, v.size() - 1);
}