퀵 정렬(Quick sort)

▶퀵 정렬

---

분할 정복 기법(Divide and conquer)으로 데이터를 정렬하는 방법이다.

1. pivot 값을 정하고 그 값보다 작거나 같은 데이터는 왼쪽으로, 큰 데이터는 오른쪽으로 이동시킨다. (정복)

2. 더이상 이동시킬 데이터가 없다면 pivot 위치 기준으로 왼쪽/오른쪽으로 분할하여 재귀적으로 수행한다. (분할)

재귀호출될 함수는 매개변수로 left, right를 가지고, left는 정복해야할 범위의 시작지점, right는 끝 지점을 의미한다.

인자 값으로 left와 pivot-1을 넘겨 [left, pivot-1] 범위에 대해 퀵 정렬을 재귀적으로 수행하고

인자 값으로 pivot+1과 right를 넘겨 [pivot+1, right] 범위에 대해 퀵 정렬을 재귀적으로 수행한다.

탈출 조건인 left >= right가 되었을 때 함수를 반환하도록 구현하면 정렬이 완료된다.

pivot 값을 가운데 값으로 정하면, 이미 정렬이 되어 있는 경우에도 균등하게 두 범위로 분할하여 정복할 수 있게 되므로 효율적이다. 

▶시간 복잡도

---

pivot 값이 매번 가장 작거나 큰 값이 되는 최악의 경우에 O(N^2)의 시간이 걸리지만 평균적으로는 Θ(NlogN)이다.

합병 정렬의 경우 O(NlogN)의 시간이 걸리지만 일반적으로 퀵 정렬이 더 빠른 성능을 보여준다.

그 이유는 개발자가 pivot을 적절하게 선택하도록 구현할 수 있고, 퀵 정렬 수행시 한 번 위치가 정해진 원소는 정렬을 위해 확인해야 할 대상에서 제외된다는 특성이 있기 때문이다.

데이터를 분할할 때 pivot 값이 매번 가장 작거나 큰 값이 되는 경우(최악) 한 쪽은 데이터가 없고 한 쪽에 모든 데이터가 몰린다. 

정렬할 데이터가 8개라고 가정했을 때 정렬을 위해 7번 분할하게 되므로 O(N)이고, 매 번 정렬되지 않은 데이터를 체크해야 하므로 O(N)이다. 따라서 전체적으로 O(N^2)의 시간이 걸린다. 

퀵 정렬은 pivot 값이 무엇이 되냐에 따라서 시간 복잡도에 영향을 끼치게 된다는 사실을 알 수 있다.

▶소스 코드