퀵 정렬은 분할정복과 비슷하지만 다른 부분이 있다.
병합 정렬을 할시에는 먼저 반반으로 쪼개고 시작을 하였지만,
나중에 반반씩 나눠지긴 하지만 1차적으로 중간값이 정해지고 반반으로 나눠진다.

퀵 정렬

맨 처음값은 pivot이라고 하고 그 다음 첫번째 값을 lowIndex라고 하고 마지막 값을 highIndex라고 한다.

여기서 lowIndex는 오른쪽으로 이동하려고 할 것이고 hightIndex는 왼쪽으로 이동하려고 할 것이다.
하지만 막 이동을 하는 것은 아니고 pivot이라는 기준값보다 작거나 같을 때까지 이동할 수 있다.

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

[1단계]
한 번 해보면 1은 5보다 작으니까 오른쪽으로 이동해 3을 가리킴

3은 5보다 작으니까 이동

7은 5보다 작지 않으니 멈추게 된다.

high도 해보면 8이 5보다 더 크니까 이동

6이 5보다 더 크니까 이동

4는 5보다 크지 않으니까 멈추게 된다.

[2단계]
low < high라면, arr[low]와 arr[high] 데이터 교체
즉, high가 low보다 왼쪽에 있으면 데이터를 교체한다.

이런식으로 바꾸고 난후 1단계를 다시 진행해주면 된다.

이런식으로 걸리게 될 것이다.

그럼 9와 2의 위치를 바꿔주면 된다.

[3단계]
high <= low면 빠져나오고, pivot과 arr[high] 교체
low가 high를 역전해버린다면 빠져나오고 pivot과 high를 바꿔준다.
그 다음에 진행하려고 하면 low와 high가 뒤바뀔 것이다.

그리고 low가 high를 역전해버렸기 때문에

이런식으로 교체를 해준다.

이렇게 한 턴이 끝나게 되면 pivot인 5의 위치는 확정이 된다.
(그리고 pivot보다 작은 값들은 왼쪽에 큰 값은 오른쪽에)

이제 이렇게 되면

이런식으로 두 개로 나눠져서 재귀적으로 퀵 정렬을 진행하게 된다.

병합정렬과는 다르게 어느정도 필요한 데이터를 모아서 정렬하는 느낌이다.

구현

void Partition(vector<int>& v, int left, int right)
{
	int pivot = v[left];
    int low = left + 1;
    int high = right;
    
    while(left <= right)
    {
		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;
}

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);
}

이런식으로 QuickSort를 구현할 수 있다.

시간복잡도를 계산을 해보면 QuickSort라는 함수는 거의 반반 나누기 때문에 O(logN)이 될 것이고
Partition은 while이 2개가 있어서 N^2이라고 생각할 수도 있지만 low가 증가하고 high가 감소하여 조건을 충복시키는 최대가 N이기 때문에 O(N)

그래서 둘이 합쳐보면 O(NlogN)이 평균적으로 나오게 된다.

마무리

결국 앞으로 정렬 알고리즘을 물어보았을 때는 평균적으로 시간복잡도가 O(NlogN)이기에 O(NlogN)이라고 기억하고 대답하자.

그리고 정렬을 실사용할 때에는 NlogN이니 많이 사용은 하면 안되지만
어차피 게임에서 정렬 기능을 만든다고 해도 버튼을 눌렀을 때만 한 번 정렬을 돌려주면 되는 부분이기에 그렇게 상관이 없을 것이다.