[Algorithm] Quick Sort (C++)

이번 글은 정렬 알고리즘 중에서 Quick Sort에 대한 글입니다.

---

퀵 정렬은 불안정 정렬에 속하며 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속합니다.

퀵 정렬은 합병정렬과 비슷하게 분할 정복(Divide And Conquer)알고리즘을 사용합니다.

C++ STL의 sort()의 경우 순차열 [b, e) 원소들을 퀵 정렬로 수행하기 때문에 평균적으로는 O(N log N)의 시간복잡도를 보장을 하며 최악의 경우 O(N^2)의 시간 복잡도를 가집니다.

 

퀵 정렬의 원리는 pivot을 임의의 인덱스에 하나잡은 뒤

Left/Right Pivot을 양 끝으로 잡고 현재 Pivot보다 작은 값들은 왼쪽으로, Pivot보다 큰 값들은 오른쪽으로 옮기면 됩니다!

이후 Pivot을 제외한 왼쪽 부분과 오른쪽 부분을 다시 분할 정복으로 같은 로직을 수행해주면 됩니다!

 

위의 수들을 기준으로 퀵정렬을 수행할 경우 4를 Pivot으로 Left를 8, Right를 5로 잡습니다. (Left = i, Right = j)

 

j는 pivot보다 작은 값이 나올 때까지 --j를 수행해줍니다. i의 경우 pivot보다 작다면 ++i를 수행해줍니다. 

현재 8이라 pivot보다 크기 때문에 그대로 놔둡니다.

그럼 위와같이 pivot과 i, j가 가르키게 됩니다.

위와 같이 i, j를 swap을 해줍니다.

이후 다시 j는  pivot보다 작은 값이 나올 때까지 --j를 수행하고, i는 pivot보다 큰 값이 나올 때까지 ++i를 수행합니다.

 

그러면 위와 같이 j와 i가 엇갈리게 됩니다. 엇갈리게 될경우 i, j를 스왑하는게 아니라 pivot과 j를 swap해줍니다.

이렇게 스왑해주게 되면 이전 pivot값(4)의 인덱스를 보면 3번인덱스 기준으로 왼쪽으로는 4보다 전부 작은값이,

오른쪽으로는 4보다 큰값이 몰리게됩니다.

현재 swap을 수행한 4를 기준으로 Divide And Conquer(분할 정복)을 수행해줍니다.

 

코드를 보도록 하겠습니다.

int _data[6] = {4, 2, 1, 5, 7, 8};

void QSort(int* Data, int Start, int End)
{
	// 원소가 1개인 경우
	if (Start >= End)
	{
		return;
	}

	int Pivot = Start;
	int Left = Pivot + 1;
	int Right = End;
	int Temp;
	
    // Left가 Right보다 작거나 같은 경우에만 계속 반복
	while (Left <= Right)
	{
    	// Left가 End보다 작고 Pivot값보다 작거나 같을 경우에만
		while (Left <= End && Data[Left] <= Data[Pivot]) ++Left;
		
        // Right가 Start보다 크고 Pivot값보다 크거나 같은 경우에만
		while (Right > Start && Data[Right] >= Data[Pivot]) --Right;

		// Left, Right 엇갈림
		if (Left > Right)
		{
			Temp = Data[Right];
			Data[Right] = Data[Pivot];
			Data[Pivot] = Temp;
		}
		// Left, Right 엇갈리지 않은 경우
		else
		{
			Temp = Data[Left];
			Data[Left] = Data[Right];
			Data[Right] = Temp;
		}
	}
	QSort(Data, Start, Right - 1);
	QSort(Data, Right + 1, End);
}