[Algorithm] Quicksort

0. Overview

---

Quicksort 알고리즘은 Divide and Conquer 방법 중 하나로, 아래와 같은 단계로 진행됩니다.
1. partition 수행(n)
2. quicksort 호출 (n/2)
3. quicksort 호출 (n/2)

가장 정직한 형태의 Divide and Counquer 방법인 MergeSort 알고리즘과 비교했을 때, combine 부분이 parttition으로 대체되어 있음을 알 수 있죠.

1. Illustration

Quicksort 알고리즘에는 pivot element라는것이 주어지는데, 알고리즘은 이를 중심으로 이보다 작은 원소는 왼쪽, 큰 왼쪽은 오른쪽으로 정렬하는 작업을 반복합니다.

2. Time Complexity

	Mergesort	Quicksort
Worst-Case	$O (nlogn)$	$O(n^2)$
Average-Case	$O (nlogn)$	$O (nlogn)$
Space Complexity	$O(n)$	$O(1)$
Stablilty	Yes	No

• Quicksort는 가장 (평균적으로) 가장 빠른 알고리즘 중 하나입니다.
• Quicksort는 Random하게 들어오는 자료에 대해 굉장한 성능을 발휘하지만, 정렬된 자료에 대해 좋지 않은 성능을 보여줍니다.
• Recursion Depth때문에, Stackoverflow를 조심해야 합니다.