정렬 알고리즘 - 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

 

퀵 정렬 이란?

 

 - 분할 정복(divide and conquer) 알고리즘 디지인 기법에 근거하여 만들어진 정렬 방법.

 

 - 정렬 대상을 반씩 줄여가며 정렬한다.

 

 - 피벗을 기준으로 정렬한다.

 

 - 피벗을 어떤 값으로 설정하냐에 따라 속도가 달라진다.

   (피벗이 중간에 해당하는 값일 경우 정렬 대상을 균등하게 나눈다)

 

 - 정렬대상에서 세 개의 데이터를 추출하고, 그 중 중간 값에 해당하는 것을 피벗으로 삼는다.

 

 - 퀵 정렬은 O(nlogn)의 시작복잡도를 가진다.(최선의 경우) // 최악의 경우 O($n^2$)

 

---

 

퀵 정렬 예시(오름차순)

 

1. 초기 상태

 

 

2. pivot을 정한다.

3. low는 pivot보다 큰 값을 찾아서 오른쪽으로, high는 pivot 보다 작은 값을 찾아서 왼쪽으로 이동한다.

4. low와 high가 정해지면, low와 high의 값을 교환한다.

5. 위 과정을 반복하다가 low와 high의 위치가 교환되는 순간을 찾는다.

 

 

 

 

6. pivot과 high의 위치를 교환한다.

 

 

7. 전 pivot인 5를 기준으로 왼쪽과 오른쪽에 각각 pivot을 정하고, 위의 과정을 반복한다.

 

 

 - left와 right가 교차되는 상황 발생하면 더 이상 정렬할 대상이 없다는 것이다.

 

 

---

 

퀵 정렬 코드(C++)

 

#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int> &vec, int left, int right)
{
	int pivot = vec[left];
	int low = left + 1;
	int high = right;
	int temp = 0;

	// low > high인 경우까지 반복
	while (low <= high)
	{
		// 피봇보다 큰 값 찾기
		while (pivot > vec[low])
			low++;

		while (pivot < vec[high])
			high--;

		// low와 high 값 위치 변경
		if (low <= high)
		{
			temp = vec[low];
			vec[low] = vec[high];
			vec[high] = temp;
		}
	}

	// 피벗(left)와 high 위치 변경
	temp = vec[left];
	vec[left] = vec[high];
	vec[high] = temp;

	return high;
}


void QuickSort(vector<int> &vec, int left, int right)
{
	int pivot;

	// 분할 가능한 경우
	if (left < right)
	{
		// 둘로 나누기(피봇을 기준으로 나눔)
		pivot = partition(vec, left, right); 

		// 왼쪽 영역 정렬
		QuickSort(vec, left, pivot - 1);

		// 오른쪽 영역 정렬
		QuickSort(vec, pivot+1, right);

	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> vec{ 7,1,8,3,5,2};

	cout << "정렬 전 : ";
	for (auto i : vec)
		cout << i << ", ";
	cout << endl;

	// right에는 크기가 아니라, 마지막 인덱스 값 전달.
	QuickSort(vec,0,vec.size()-1);

	cout << "정렬 후 : ";
	for (auto i : vec)
		cout << i << ", ";
	cout << endl;
	
	return 0;
}

실행 결과