4) 퀵 정렬 (Quick Sort)

---

앞서 했던 정렬들의 경우 시간 복잡도가 O(N^2)을 가져 데이터의 갯수가 10만 개만 넘어가도 일반적인 상황에서 매우 사용하기 어려운 알고리즘이다.
그래서 더욱 빠른 알고리즘이 필요한데 대표적인 것이 퀵 정렬이다.

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

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

#include <iostream>
using namespace std;

void quickSort(int* data, int start, int end) {
	if (start >= end) {
		return;
	}
	int key = start;
	int i = start + 1, j = end, temp;
	while (i <= j) // 엇갈리 때까지 반복
	{
		while (i <= end && data[i] <= data[key]) // 왼쪽으로부터 큰 값 찾기
		{
			i++;
		}
		while (j > start && data[j] >= data[key]) // 오른쪽으로부터 작은 값 찾기
		{
			j--;
		}
		if (i > j) // 엇갈린 상태 키 값과 교체
		{
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		}
		else
		{
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}

	quickSort(data, start, j - 1);
	quickSort(data, j + 1, end);
}

int main() {

	int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };
	
	quickSort(array, 0, 9);

	for (int i = 0; i < 10; i++)
	{
		cout << array[i];
	}

}

---

1) 배열을 반으로 나눈 후 왼쪽으로부터 기준 값보다 큰 값, 오른쪽으로부터 작은 값을 찾는다.
2) 찾으면 왼쪽 키 값과 오른쪽 키 값을 교체한다.
3) 이 작업을 반복하다가 왼쪽, 오른쪽이 교차하면 키 값을 교차된 자리에 키 값과 해당 값을 교차한다.

이렇게 계속 이 작업들을 반복한다.

퀵 정렬은 분할 정복 알고리즘이다.

시간 복잡도를 살펴보면
10개의 값이 있다고 가정,

N^2 = 10 * 10 = 100

1 2 3 4 5 = 5 5 = 25
6 7 8 9 10 = 5 5 = 25
총 50

즉 시간복잡도는 O(N*logN)으로 O(N^2)보다 훨씬 빠르다.

하지만 이러한 퀵 정렬에도 최악의 조건이 존재한다.
최악의 시간복잡도는 O(N^2)이다.

예시로
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
위와 같이 이미 정렬되어 있을 경우 시간복잡도는 O(N^2)에 가깝다.
이 경우에는 삽입 정렬이 훨씬 빠르다.

이렇듯 항상 이것이 빠르다 라는 말은 틀린말이다.
항상 주어진 값과 상황에 따라서 정렬 알고리즘을 사용해야 한다.