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

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

---

특정한 값(Pivot)을 기준으로 큰 숫자와 작은 숫자를 나누자!!!

다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하자!

1, 10, 5, 8, 7, 6, 3, 4, 2, 9

1 10 5 8 7 6 3 4 2 9 // 맨 앞을 기준으로 왼쪽에서부터 큰값을 찾고 오른쪽에서부터 작은 값을 찾는다.

                                // 큰값 10, 작은값 없음 다음으로 피벗을 넘김

1 10 5 8 7 6 3 4 2 9 //기준 값 10, 큰값 없음 작은값 5

1 5 10 8 7 6 3 4 2 9 

⁞

1 5 8 7 6 3 4 2 9 10 //10보다 큰 값이 없기 때문에 계속 작은 값과 위치가 바뀌어서 맨뒤로감

1 5 8 7 6 3 4 2 9 10 //기준 값 5,  큰값 8 작은값 2

1 5 2 7 6 3 4 8 9 10 //큰값 7, 작은값 4

1 5 2 4 6 3 7 8 9 10 //큰값 6, 작은값 3

1 5 2 4 3 6 7 8 9 10 //큰값 6, 작은값 3 엇갈린 상황 발생

1 3 2 4 5 6 7 8 9 10 //5와 3을 바꿔줌

1 3 2 4 5 6 7 8 9 10 //양옆에 1과 6을 기준값으로 잡고 정렬

⁞

1 2 3 4 5 6 7 8 9 10

소스코드 구현 (C++)

#include <iostream>
using namespace std;
//퀵정렬
void QuickSort(int* arr, int start, int end)
{
	//원소가 1개인 경우
	if (start >= end)
	{
		return;
	}
	int pivot = start;
	int i = pivot + 1; //큰값을 찾기위한 수
	int j = end; //작은값을 찾기위한 수
	int temp;

	while (i <= j) //엇갈릴 때까지
	{
		//i가 기준값보다 작다면 한칸씩 오른쪽으로 이동
		while (arr[i] <= arr[pivot])
		{
			i++;
		}
		//j가 기준값보다 크다면 한칸씩 왼쪽으로 이동
		while (arr[j] >= arr[pivot] && j > start)
		{
			j--;
		}
		//i와 j가 교차한다면
		if (i > j)
		{
			temp = arr[j];
			arr[j] = arr[pivot];
			arr[pivot] = temp;
		}
		
		else
		{
			temp = arr[j];
			arr[j] = arr[i];
			arr[i] = temp;
		}
	}
	cout << "QuickSort [";
	for (int i = 0; i < 10; i++)
	{
		cout << arr[i] << ", ";
	}
	cout << "]" << endl;
	QuickSort(arr, start, j - 1);
	QuickSort(arr, j + 1, end);
}

int main()
{
	int temp;
	int arr[10] = { 1, 10, 5, 8, 7, 6, 3, 4, 2, 9 };

	QuickSort(arr, 0, 9);
	
	for (int i = 0; i < 10; i++)
	{
		cout << arr[i] << ", ";
	}
	return 0;
}

출력 결과

 

시간 복잡도 계산

퀵 정렬은 대표적인 '분할 정복' 알고리즘으로 평균 속도가 O(N * logN)이다.

데이터의 개수 N 그리고 반씩 분할하기 때문에 logN 즉, 이 두 경우를 합친 N * logN이 되는 것이다.

 

---

퀵정렬은 평균 시간 복잡도는 O(N*logN)이다. 평균이란 말은 평균이 아닐때도 있다는 것을 의미하며, 최악의 경우가 있을 수 있다는 것이다. 다음 상황을 살펴보자!

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

1 2 3 4 5 6 7 8 9 10 // 10번

1 2 3 4 5 6 7 8 9 10 // 9번

1 2 3 4 5 6 7 8 9 10 // 8번

⁞

1 2 3 4 5 6 7 8 9 10 

10 + 9 + 8 + 7 + ... + 2 + 1

= N(N + 1)/2

즉, N^2

위 처럼 이미 정렬이 되어있는 상황은 퀵정렬 시 기존에 비효율적인 정렬들과 마찬가지로 O(N^2)의 시간복잡도를 확인할 수 있었으며 오히려 삽입정렬이 더 빠른 경우가 될 수 있음을 확인할 수 있었다.

기본적으로 가장 빠른 정렬은 퀵정렬이지만 이미 정렬이 된 상황에서는 그렇지 않다는 사실을 알아두자!!!!