퀵 정렬
값 하나를 골라 피벗(기준값)으로 삼고, 더 작은 값은 왼쪽으로, 더 큰 값은 오른쪽으로 옮깁니다. 그다음 양쪽에서 같은 일을 반복합니다.
- 최선 Ω(n log n)
- 평균 Θ(n log n)
- 최악 O(n²)
- 메모리 O(log n)
- 불안정
- 추가 메모리 없음
용어 설명
- 최선: 이 알고리즘에 가장 쉬운 입력일 때, 리스트 크기 n에 따라 시간이 늘어나는 정도.
- 평균: n에 따라 시간이 늘어나는 보통의 정도. n²이면 값의 개수가 두 배일 때 시간은 약 네 배이고, n log n은 훨씬 천천히 늘어납니다.
- 최악: 가장 어려운 입력에서 늘어나는 정도. 속도가 절대 떨어지면 안 될 때 중요합니다.
- 메모리: 리스트 외에 필요한 추가 메모리 양. 1은 변수 몇 개, n은 리스트 복사본 하나를 뜻합니다.
- 안정: 같은 값 두 개가 원래 순서를 유지합니다. 레코드의 한 필드로 정렬할 때 중요합니다.
- 추가 메모리 없음: 두 번째 리스트 없이 리스트 안에서 바로 정렬합니다.
- 비교 중
- 이동 중
- 피벗
- 제자리
비교 횟수 교환 횟수
재생을 누르면 정렬이 진행되며 비용이 늘어나는 모습이 선으로 보입니다
재생을 누르거나 한 단계씩 진행하세요.
스페이스바: 재생 또는 일시정지. 좌우 화살표 키: 단계 이동. Home과 End 키: 처음과 끝으로 이동.
해 보세요: 역순 리스트를 골라 보세요. 피벗이 늘 남은 값 중 최솟값이나 최댓값이라서, 나눌 때마다 한쪽이 비고 비용이 n²에 가까워집니다.
작동 방식
여기서는 구간의 마지막 값이 피벗입니다. 왼쪽에서 오른쪽으로 가면서 피벗보다 크지 않은 값을 모두 왼쪽으로 교환합니다. 그다음 피벗을 두 그룹 사이에 놓으면, 피벗은 그 자리에서 더는 움직이지 않습니다. 양쪽 그룹도 같은 방법으로 정렬합니다.
언제 쓰면 좋을까
실제로 가장 빠른 정렬 방법 중 하나이고, 추가 메모리도 거의 필요 없습니다. 하지만 나쁜 피벗을 계속 고르면 느려집니다. 이미 정렬된 리스트가 그런 예입니다. 실제 구현은 피벗을 더 신중하게 고릅니다.