TL;DR (세 줄 요약)퀵 정렬은 평균 O(n log n)으로 빠른 정렬 알고리즘입니다. 하지만 피벗(기준 값)을 잘못 고르면 이미 정렬된 배열에서 O(n²)까지 느려집니다.피벗을 기준으로 작은 값과 큰 값을 나누고, 나뉜 두 구간에 같은 일을 반복합니다. 한쪽으로만 나뉘면 비교 횟수가 (n-1)+(n-2)+…+1이 되어 n의 제곱에 비례합니다.무작위 피벗, 미디언-오브-쓰리, 작은 구간의 삽입 정렬 전환, 재귀 깊이 줄이기, Introsort로 최악의 경우를 피합니다.한 기업의 필기 테스트에서 나온 문제를 계기로 퀵 정렬을 다시 정리했습니다. 정렬은 값을 크기 순서대로 늘어놓는 일입니다. 이 글은 퀵 정렬의 기본 개념, 동작 원리, 최악의 경우가 생기는 이유, 그것을 줄이는 방법을 순서대로 설명합니다..