컴퓨터알고리즘#9
LeeMir, 14 April 2021
퀵 정렬
퀵 정렬
- 분할통치법에 기초한 정렬 알고리즘
- 기준 원소 p(pivot, 보통 마지막 원소)를 택해 리스트를 p보다 작은(LT), p와 같은(EQ), p보다 큰(GT) 부분으로 분할
- 분할 후 각 분할된 집합을 정렬, 그리고 합병
- 기준원소 선택
- 결정적이며 쉬운 방법
- 맨 앞, 맨 뒤, 중간
- 결정적이며 조금 복잡한 방법
- 맨 앞, 중간, 맨 뒤 위치의 세 원소의 중앙값
- 0/4, 1/4, 2/4, 3/4, 4/4 위치 다섯 원소의 중앙값
- 전체 원소의 중앙값
- 기준원소의 선택에 따라 분할 결과 및 퀵 정렬 수행 성능에 영향을 미침
- 결정적이며 쉬운 방법
- 퀵 정렬 트리
- ㅇ
- 시간복잡도
- 최악의 경우
- pivot을 고를 때마다 유일한 최댓값 / 최솟값일 경우
- O(n^2)
- LT와 GT의 크기가 모두 전체의 3/4보다 작은 것이 좋은 호출임
- O(n log n)
- 최악의 경우
무작위 퀵 정렬
- 퀵 정렬의 결정적 버전에서는 pivot을 마지막 원소를 선택했음
- 새로운 규칙 : 무작위 원소를 선택
제자리 퀵 정렬
- pivot 선택 후 포인터 두 개를 리스트의 양쪽 끝에 생성
- 왼쪽 포인터는 오른쪽으로, 오른쪽 포인터는 왼쪽으로 이동
- 왼쪽 포인터는 pivot보다 큰 값을 만나면 그 곳에서 정지, 오른쪽 포인터는 pivot보다 작은 값을 만나면 그 곳에서 정지
- 둘 다 정지하면 두 값을 교환 후 계속 진행
- 두 포인터가 교차하면 정지 후 pivot에 가까운 원소가 pivot과 교환