소개
어떤 문제를 해결하나요
퀵 정렬은 가장 널리 쓰이는 정렬 방식 가운데 하나입니다. 평균적으로 빠르고 코드로 표현하기도 쉽기 때문입니다. 퀵 정렬은 문제를 나누는 또 다른 방법을 보여 줍니다. 가운데에서 자르는 대신, 값 하나를 골라 그 값을 기준으로 나눕니다.
일상 속 비유
퀵 정렬은 책 한 권을 기준으로 골라 책들을 높이 순서로 정리하는 것과 같습니다. 기준보다 낮은 책은 모두 왼쪽 더미에, 높은 책은 모두 오른쪽 더미에 놓고, 높이가 같은 책은 가운데에 둡니다. 그런 다음 양쪽 더미를 각각 같은 방법으로 정리하고, 더미들을 다시 이어 붙입니다.
pivot = values[len(values) // 2]📕 기준으로 삼을 책 한 권 고르기lower = [... if value < pivot]⬅️ 더 낮은 책은 왼쪽으로higher = [... if value > pivot]➡️ 더 높은 책은 오른쪽으로quick_sort(lower) + equal + quick_sort(higher)📚 양쪽을 각각 정리한 뒤 더미 이어 붙이기퀵 정렬은 기준이 되는 값인 피벗(pivot)을 하나 고르고, 나머지 항목을 피벗보다 작은 것과 큰 것으로 나눕니다. 그런 다음 각 부분을 재귀로 정렬해서 이어 붙입니다. 평균 O(n log n) 시간이 걸립니다.
핵심 포인트
if len(values) <= 1:은 기저 사례입니다. 이런 리스트는 이미 정렬되어 있습니다.pivot = values[len(values) // 2]는 가운데 값을 피벗으로 삼습니다.lower,equal,higher는 피벗을 기준으로 값을 나눠 담습니다. 피벗과 같은 값들은equal에 함께 모입니다.quick_sort(lower) + equal + quick_sort(higher)는 양쪽을 정렬한 뒤 세 리스트를 이어 붙입니다.
언제 사용하나요?
- 분할(partition)과 재귀를 배울 때.
- 여러 언어와 라이브러리에 들어 있는 범용 제자리 정렬(피벗을 신중하게 고르는 경우).
- 중앙값 찾기 같은 선택 문제(quickselect가 같은 분할 방법을 씁니다).
필요 없는 경우
- 일반적인 Python 코드:
sorted()가 더 빠르고, 같은 값의 순서를 유지하는 안정 정렬입니다. - 최악의 경우에도 속도가 보장되어야 할 때: 피벗을 잘못 고르면 퀵 정렬은
O(n²)이 됩니다. 병합 정렬은 그럴 일이 없습니다.
Python의 퀵 정렬(quick sort) 시각화
O(n log n)재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.
예제 코드
def quick_sort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
higher = [value for value in values if value > pivot]
return quick_sort(lower) + equal + quick_sort(higher)
print(quick_sort([10, 7, 8, 9, 1, 5]))
실행 결과
[1, 5, 7, 8, 9, 10]
코드 설명
읽기 쉬운 이 버전은 가운데 요소를 피벗으로 고르고, 리스트 컴프리헨션으로 lower, equal, higher 세 리스트를 만듭니다. 결과는 quick_sort(lower), equal, quick_sort(higher)를 이어 붙인 것입니다. 평균 복잡도는 O(n log n)이지만, 피벗을 잘못 고르면 O(n²)까지 느려질 수 있습니다.
값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.
연습 문제
아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.
- 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
- 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
- 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
자주 하는 실수
피벗과 같은 값을 빠뜨리기
<와 >로만 나누면 피벗과 값이 같은 항목들이 사라집니다.
return quick_sort(lower) + [pivot] + quick_sort(higher)
return quick_sort(lower) + equal + quick_sort(higher)
이 레슨을 마쳤나요?
학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
모든 챌린지