• 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘
• 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미침
• 평균 시간 복잡도는 O(nlogn)이고, 최악의 경우에는 시간 복잡도가 O(n²)
• 퀵 정렬의 시간 복잡도는 비교적 준수하고, 재귀 함수의 형태로 직접 구현

[019] K번째 수 구하기

• https://www.acmicpc.net/problem/11004
• 퀵 정렬은 pivot의 선택에 따라 최악의 시간 복잡도가 n²이므로 해당 문제에서는 병햡 정렬 등을 이용하는 게 더 안전
• pivot을 정하는 방법
  • pivot == K: K번째 수를 찾은 것이므로 알고리즘을 종료
  • pivot > K: pivot의 왼쪽 부분에 K가 있으므로 왼쪽(S ~ pivot - 1)만 정렬을 수행
  • pivot < K: pivot의 오른쪽 부분에 K가 있으므로 오른쪽(pivot + 1 ~ E)만 정렬을 수행