차이점 1 : 병합 정렬은 그냥 두 부분으로 나누는 반면, 퀵 정렬은 분할할 때, 기준 아이템(pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치
차이점 2 : 각 부분 정렬이 끝난 후, 병합 정렬은 "병합"이란 후처리 작업이 필요하나, 퀵 정렬은 필요 없음
퀵 정렬 과정
알고리즘
def quick_sort(a, low, high): # (리스트, 시작 인덱스, 끝 인덱스)
if low < high:
pivot = partition(a,low,high)
quick_sort(a, low, pivot-1)
quick_sort(a, pivot+1, high)
Hoare-Partition 방식
def partition(a, pivot, high):
i = pivot + 1
j = high
while True:
while i < high and a[i] < a[pivot]:
i += 1
while j > pivot and a[j] > a[pivot]:
j -= 1
if j <= i:
break
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
a[pivot], a[j] = a[j], a[pivot]
return j
P(피봇)값들 보다 큰 값은 오른쪽, 작은 값들은 왼쪽 집합에 위치하도록 한다.
피봇을 두 집합의 가운데에 위치시킨다.
피봇 선택
왼쪽 끝, 오른쪽 끝, 임의의 세개 값중에 중간 값
왼쪽 끝(3)을 피봇으로 설정하고 퀵 정렬 진행
i는 왼쪽 끝에서부터 시작하며 피봇보다 큰 값을 탐색
j는 오른쪽 끝에서부터 시작하며 피봇보다 작은 값을 탐색
만일 i와 j가 탐색 중 조건에 일치하는 값을 탐색한다면, i와 j 자리의 숫자 자리 교체
위의 과정을 반복하면 한 사이클이 종료된 후, 어떠한 지점을 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값이 위치
해당 경계 값과 피봇의 자리를 교체하고 피봇을 중심으로 양쪽 숫자들에 대해 퀵 정렬을 재귀적으로 수행
i는 피봇값 3보다 큰 4를 탐색
j는 피봇값 3보다 작은 1을 탐색
4와 1의 자리 교체
i와 j가 계속적으로 탐색을 진행하다 보면, 교차하는 지점이 발생(큰 값, 작은 값을 분리하는 경계점이기도 함)
그 때 피봇과 교환
3에 대해서는 더 이상 탐색을 진행할 필요가 없음
이미 왼쪽과 오른쪽으로는 대소비교가 완벽하게 완료되었기 때문
3을 기준으로 왼쪽의 1, 2와 오른쪽의 6, 9, 4, 8, 7, 5 에 대해서 정렬을 수행
피봇은 왼쪽 끝 값인 1
i는 왼쪽 끝 값인 1
j는 오른쪽 끝 값인 2
i와 j가 탐색을 진행하면 바로 서로 교차해버림
탐색이 종료되고 1은 해당 j 번째 자리에 고정, 2 또한 최소 크기의 부분집합이므로 해당 자리에 고정
1, 2, 3에 대해서는 더 이상의 탐색은 필요 없음
같은 과정으로 3의 오른쪽 숫자들에 대해서 퀵 정렬 수행
피봇 : 6 / i : 6 / j : 5 로 탐색 시작
Lomuto partition 방식
알고리즘
def partition(a, p, r):
x = a[r]
i = p - 1
for j in range(p, r-1):
if a[j] <= x:
i += 1
a[i], a[j] = a[j], a[i]
a[i+1], a[r] = a[r], a[i+1]
return i + 1
