이 글은 이것이 취업을 위한 코딩테스트다 with python편을 보고 작성하였습니다.
퀵 정렬
1. 퀵 정렬의 개요
퀵 정렬은 '기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방식'입니다. 정확히 말하면 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작합니다.
퀵 정렬에서는 피벗(Pivot)이 사용되는데, 큰 숫자와 작은 숫자를 교환하기 위한 '기준'이 됩니다. 이 피벗을 어떻게 설정할 것인지에 따라 여러 가지 방식으로 퀵 정렬을 구분하는데, 호어 분할(리스트에서 첫 번째 데이터를 피벗으로 정한다) 방식을 사용하겠습니다.
2. 퀵 정렬의 예시
리스트에서 첫 번째 데이터를 피벗으로 정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾습니다. 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환합니다. 이러한 과정을 반복하면 '피벗'에 대하여 정렬이 수행됩니다.
퀵 정렬은 파트를 3개로 나누어 보겠습니다.
1️⃣ 파트
- 리스트의 첫 번째 데이터를 피벗으로 설정하므로 피벗은 '5'입니다. 이후 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택됩니다. 이 두 데이터의 위치를 변경하면 됩니다
- 그다음 다시 피벗보다 큰 데이터와 작은 데이터를 각각 찾습니다. 찾은 뒤에는 두 값의 위치를 서로 변경하는데, 현재 '9'와 '2'가 선택되었으므로 이 두 데이터의 위치를 변경합니다.
- 그다음 다시 피벗보다 큰 데이터와 작은 데이터를 찾습니다. 단, 현재 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈렸습니다. 이렇게 두 값이 엇갈린 경우에는 '작은 데이터와', '피벗'의 위치를 변경합니다. 즉 작은 데이터 '1'과 피벗 '5'의 위치를 서로 변경합니다.
- 이와 같이 피벗이 이동한 상태에서 왼쪽 리스트와 오른쪽 리스트를 보면 피벗인 '5'의 왼쪽에 있는 데이터는 모두 '5'보다 작고, 오른쪽에 있는 데이터는 모두 '5'보다 크다는 특징이 있습니다. 이러한 상태에서 원래 피벗인 '5'를 제외하고 왼쪽의 리스트와 오른쪽의 리스트에도 똑같이 피벗을 설정하여 동일한 방식으로 정렬을 수행하면 전체 리스트에 대해 모두 정렬이 이루어 집니다.
2️⃣ 파트
- 왼쪽 리스트에서는 다음과 같이 정렬이 진행되고 구체적인 정렬 과정은 위와 같습니다.
3️⃣ 파트
- 오른쪽 리스트에서는 다음 그림과 같이 정렬이 진행되며 구체적인 정렬 과정은 위와 같습니다.
퀵 정렬은 이처럼 특정한 리스트에서 피벗을 설정하여 정렬을 수행한 이후에, 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행합니다. 이를 재귀 함수 형태로 작성하면 구현이 매우 간결해집니다. 재귀함수와 동작원리가 같다면, 종료 조건이 필요합니다. 그렇지 않으면 무한하게 재귀함수를 호출하기 때문입니다. 퀵 정렬의 종료 조건은 현재 리스트의 데이터 개수가 1개인 경우입니다. 리스트의 원소가 1개라면, 이미 정렬이 되어 있다고 간주할 수 있으며 분할이 불가능합니다.
3. 퀵 정렬의 소스 코드
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
if start >= end: # 원소의 개수가 1개인 경우 종료
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], array[pivot] = array[pivot], array[right]
else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
array[left], array[right] = array[right], array[left]
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
# 엇갈린 부분에서 right의 위치(작은 값의 위치)가 pivot가 바뀌었으므로 그 인덱스의 왼쪽과 오른쪽으로 분리
quick_sort(array, start, right - 1)
quick_sort(array, right + 1, end)
quick_sort(array, 0, len(array) - 1)
print(array)위와 같은 방식은 가장 직관적인 형태의 퀵 정렬 소스코드입니다.
아래는 파이썬의 장점을 살려 작성한 퀵 정렬 코드입니다. 위의 방식보다는 비교 연산 횟수가 증가해 시간 면에서는 조금 비효율적입니다.
array = [7, 5, 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))4. 퀵 정렬의 시간 복잡도
선택 정렬과 삽입 정렬의 시간 복잡도는 O(N^2)입니다. 선택 정렬과 삽입 정렬은 최악의 경우에도 항상 시간 복잡도 O(N^2)을 보장합니다. 퀵 정렬은 그에 반해 평균 시간 복잡도는 O(NlogN)입니다.
퀵 정렬의 평균 시간 복잡도 O(NlogN)이지만 최악의 경우 시간 복잡도는 O(N^2)입니다. 데이터가 무작위로 입력되어 있으면 퀵 정렬은 빠르게 동작할 확률이 높습니다. 하지만 호어 분할 방식(피벗을 리스트의 가장 왼쪽 데이터로 삼는 것)을 이용하면 '이미 데이터가 정렬되어 있는 경우'에는 매우 느리게 동작합니다.
삽입 정렬은 이미 데이터가 정렬되어 있는 경우에는 매우 빠르게 동작한다고 했는데, 퀵 정렬은 그와 반대된다고 이해하면 됩니다.
