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

[Sort] 퀵 정렬(Quick Sort) 알고리즘

 

퀵 정렬(Quick Sort) 알고리즘이란?

• 찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)가 개발한 정렬 알고리즘이다
• 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속하며, 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속한다.
• N개의 데이터를 정렬할 때, 최악의 경우에는 O(N^2)번의 비교를 수행하고, 평균적으로 O(N log N)번의 비교를 수행한다.
• 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다.
• 퀵 정렬은 정렬을 위해 평균적으로 O(log N)만큼의 memory를 필요로한다. 최악의 경우 O(n)의 공간복잡도를 보인다.
• 퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘의 하나로, 다른 정렬 방법보다 평균적으로 빠르기 때문에 퀵 정렬이라는 이름이 붙었다.

분할 정복(Divide and Conquer) 알고리즘이란?

정렬할 리스트를 분할하고 분할되어 있는 리스트 안에서 차례대로 정렬하는 방법이다.

• 분할 (Divide)
  정렬할 배열을 기준점을 기준으로 2개의 부분배열로 분할한다.
• 정복 (Conquer)
  부분 배열을 정렬한다.
• 결합 (Combine)
  정렬된 부분 배열들을 하나의 배열에 합병한다.

 

퀵 정렬(Quick Sort) 알고리즘 구현 과정

1. 리스트 안에 있는 요소를 하나 선택한다. 이렇게 고른 원소를 피벗(Pivot) 이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 왼쪽으로 옮기고, 피벗보다 큰 요소들은 오른쪽으로 옮긴다.
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
4. 부분 리스트가 분할이 불가능할 때까지 이를 반복한다.

#include <iostream>

using namespace std;

void QuickSort(int list[], int left, int right);
void Swap(int *x, int *y);


int main()
{
	int quickData[] = { 5, 7, 3, 2, 6, 4, 8, 1 };

	QuickSort(quickData, 0, 7);

	for (int i = 0; i < 8; i++) {
		cout << quickData[i] << ", ";
	}
}

void QuickSort(int list[], int left, int right)
{
	// 원소가 1개인 경우
	if (left >= right)
		return;

	int pivot = list[left];
	int low = left+1;
	int high = right;
	int temp;

	// low와 high가 교차할 때까지 반복(low < high)
	while (low <= high)
	{
		// list[low]가 피벗보다 작으면 low를 증가
		while (low <= high && list[low] < pivot)
		{
			low++;
		}

		// list[high]가 피벗보다 작으면 high를 증가
		while (high >= low && list[high] > pivot)
		{
			high--;
		} 

		if (low < high)
		{
			// low와 high가 교차하지 않았다면 list[low]와 list[high]를 교환
			Swap(&list[low], &list[high]);
		}
		else
		{
			// list[left](pivot)와 list[high]를 교환
			Swap(&list[left], &list[high]);
		}
	}

	QuickSort(list, left, high-1);	// 왼쪽 분할 리스트
	QuickSort(list, high+1, right);	// 오른쪽 분할 리스트
}

void Swap(int* x, int* y)
{
	int temp = *x;
	*x = *y;
	*y = temp;
}

 

 

 

최악의 시간복잡도를 방지하기 위한 방법 

1. 랜덤화
   배열의 랜덤한 두 개의 index를 뒤바꾸어주는 방식으로 배열이 정렬되어 있지 않도록 만든다.
2. 랜덤 기준점 선택
   기준점을 난수를 발생시켜 선택하는 방법으로, 정렬되었거나, 정렬에 가까운 배열에서 최악을 선택하는 횟수가 적어질 것이다.
3. Median Of Three Pivot
   기준점을 선택할 때 3개의 원소를 후보로 두고 그 중간 값을 선택하는 방법으로 이렇게 기준점을 선택하면 최악의 경우는 반드시 피할 수 있다.