퀵 정렬은 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법
합병정렬과 동일? - 다르다
합병정렬은 그냥 두 부분으로 나누는 반면, 퀵정렬은 분할할 때, 기준키 중심으로 작은 값과 큰 값을 위치
각 부분 정렬이 끝난 후, 합병정렬은 '합병'이란 후처리 작업 진행, 퀵정렬은 필요하지 않음
알고리즘
def quickSort(arr, begin, end):
if begin < end:
p = partition(arr, begin, end)
quickSort(arr, begin, p-1)
quickSort(arr, p+1, end)
def partition (arr, begin, end):
pivot = (begin + end) // 2
L = begin
R = end
while L < R:
while(arr[L] < arr[pivot] and L < R):
L += 1
while(arr[R] >= arr[pivot] and L < R):
R -= 1
if L < R:
if L == pivot:
pivot = R
arr[L], arr[R] = arr[R], arr[L]
arr[pivot], arr[R] = arr[R], arr[pivot]
return R
퀵 정렬 과정
arr = [69, 10, 10, 2, 16, 8, 31, 22]
원소 개수가 8개이므로 네 번째 자리에 있는 원소 2를 첫 번째 피봇으로 선택하고 퀵 정렬 시작
피봇 2의 왼쪽 부분 집합은 공집합이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합에 대해서 퀵 정렬 수행
피봇 16의 왼쪽 부분 집합에서 원소 10을 피봇으로 선택하여 퀵 정렬 수행
피봇 10의 확정된 위치에서의 왼쪽 부분 집합은 원소가 한 개이므로 퀵 정렬을 수행하지 않음
오른쪽 부분 집합은 공집합이므로 역시 퀵 정렬을 수행하지 않음
피봇 30의 확정된 위치에서 왼쪽 부분 집합의 원소가 한 개이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분집합에 대해서만 퀵 정렬 수행
