퀵 정렬
기준 데이터를 설정하고 그 기준보다 작은 데이터의 위치를 바꾸는 방법입니다.
일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘입니다.
병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘입니다.
가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정합니다.
동작 예시
[Step 0] 현재 피벗의 값은 5입니다. 왼쪽에서부터 5보다 큰 데이터를 선택하므로 7이 선택되고, 오른쪽에서부터 5보다 작은 데이터를 선택하므로 4가 선택됩니다. 이제 이 두 데이터의 위치를 서로 변경합니다.
[Step 1] 현재 피벗의 값은 5입니다. 왼쪽에서부터 5보다 큰 데이터를 선택하므로 9가 선택되고, 오른쪽에서부터 5보다 작은 데이터를 선택하므로 2가 선택됩니다. 이제 이 두 데이터의 위치를 서로 변경합니다.
[Step 2] 현재 피벗의 값은 5입니다. 왼쪽에서부터 5보다 큰 데이터를 선택하므로 6이 선택되고, 오른쪽에서부터 5보다 작은 데이터를 선택하므로 1이 선택됩니다.
단, 이처럼 위치가 엇갈리는 경우 피벗과 작은 데이터의 위치를 서로 변경합니다.
[분할 완료] 이제 5의 왼쪽에 있는 데이터는 모두 5보다 작고, 오른쪽에 있는 데이터는 5보다 크다는 특징이 있습니다.
이렇게 피벗을 기준으로 데이터를 나누는 작업을 분할(Divide)이라고 합니다.
[왼쪽 데이터 묶음] 왼쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행합니다.
이러한 과정을 반복하면 전체 데이터에 대해 정렬이 수행됩니다.
시간 복잡도
퀵 정렬은 평균의 경우 O(NlogN)의 시간복잡도를 가집니다.
너비 X 높이 = N x logN = NlogN
하지만 최악의 경우 O(N^2)의 시간복잡도를 가집니다.
소스코드
[일반적인 방식]
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
if start >= end:
return
pivot = start
left = start + 1
right = end
while (left <= right):
# 피벗보다 큰 데이터를 찾을 때까지 반복
while(left <= end and array[left] <= array[pivot]):
left += 1
# 피벗보다 작은 데이터를 찾을 때까지 반복
while(right > start and array[right] >= array[pivot]):
right += 1
if (left > right) # 엇갈렸다면 피벗과 작은 데이터 교체
array[right], pivot = pivot, array[right]
else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
array[left], array[right] = array[right], array[left]
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quick_sort(array, start, right-1)
quick_sort(array, right+1, end)
quick_sort(array, 0, len(array)-1)
print(array)
# 실행 결과
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9][파이썬의 장점을 살린 방식]
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array):
if len(array) <= 1:
return array
pivot = array[0]
tail = array[1:]
left_side = [x for x in tail if x <= pivot]
right_side = [x for x in tail if x > pivot]
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array))
# 실행 결과
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]