퀵 정렬(Quick Sort) 알고리즘에 대해 설명해주세요.

퀵 정렬은 피벗(pivot) 원소를 기준으로 배열을 두 부분으로 분할하고 재귀적으로 정렬하는 분할 정복 알고리즘입니다. 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분리하고, 각 부분을 같은 방식으로 재귀 정렬합니다. 평균 시간복잡도는 O(n log n)이지만, 피벗이 항상 최솟값이나 최댓값이 되는 최악의 경우 O(n²)이 됩니다. 이를 방지하기 위해 랜덤 피벗 선택이나 중간값(median-of-three) 방식을 씁니다. 같은 O(n log n)인 병합 정렬과 비교하면 퀵 정렬은 추가 메모리가 거의 필요 없고 캐시 효율이 높아 실제 성능이 더 빠른 경우가 많습니다.

퀵 정렬은 평균 성능이 좋지만 피벗 선택이 실제 성능을 결정하는 핵심 변수입니다.