Do it! 자료구조와 함께 배우는 알고리즘 입문 [파이썬] #6장 정렬 알고리즘
목차
- 06-5 셸 정렬
- 06-6 퀵 정렬
- 06-7
- 06-8
- 06-9
✔06-5
✔06-6 퀵 정렬
퀵 정렬 : 가장 빠른 정렬 알고리즘
키가 168cm인 학생 A를 선택하여 이 학생을 기준으로 168cm 미만인 그룹과, 168cm이상인 그룹으로 나눕니다. 이때 그룹을 나누는 기준을 피벗이라고 합니다.
pl 피벗(x) pr
| 5 | 7 | 1 | 4 | 6 | 2 | 3 | 9 | 8 |
a[pl] >= x가 성립하는 원소를 찾을 때까지 pl을 오른쪽 방향으로 스캔합니다.
a[pr] <= x가 성립하는 원소를 찾을 때까지 pr를 왼쪽 방향으로 스캔합니다.
pl과 pr은 다음 그림에서 정지합니다. pl은 피벗 이상인 원소에, pr는 피벗 이하인 원소에 위치합니다. 여기서 pr과 pr가 위치하는 원소 a[pl]과 a[pr]의 값을 교환합니다. 그러면 피벗 이하인 값은 왼쪽으로 이동하고, 피벗 이상인 값을 오른쪽으로 이동합니다.
pl pr
| 5 | 7 | 1 | 4 | 6 | 2 | 3 | 9 | 8 |
다시 스캔을 계속하면 pl과 pr는 다음 그림의 위치에서 정지하고, 원소 a[pl]과 a[pr]의 값을 교환합니다.
pl pr
| 5 | 7 | 1 | 4 | 6 | 2 | 3 | 9 | 8 |
다시 스캔을 계속하면 다음 그림처럼 pl과 pr가 서로 교차합니다.
pr pl
| 5 | 7 | 1 | 4 | 2 | 6 | 3 | 9 | 8 |
pl과 pr가 교차하면 이로써 그룹을 나누는 과정이 끝나고, 배열은 두 그룹으로 나뉩니다.
피벗 이하인 그룹 : a[0], a[pl - 1]
피벗 이상인 그룹 : a[pr + 1], a[n - 1]
피벗과 일치하는 그룹 : a[pr + 1], a[pl - 1]
✔06-7
✔06-8