퀵 정렬(Quick Sort)

**#Goal**

• Quick Sort에 대해 설명할 수 있다.
• Quick Sort 과정에 대해 설명할 수 있다.
• Quick Sort을 구현할 수 있다.
• Quick Sort의 시간복잡도와 공간복잡도를 계산할 수 있다.
• Quick Sort의 최악인 경우를 개선시킬 수 있다.

**#Abstract**

Quick Sort은 분할 정복(divide and conquer) 방법 을 통해 주어진 배열을 정렬한다.

• [분할 정복(divide and conquer) 방법] 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

Quick Sort은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 또한 Merge Sort와 달리 Quick Sort는 배열을 비균등하게 분할한다.

**#Process (Ascending)**

1. 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다.

• 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.