퀵소트
피벗의 올바를 위치를 찾아가면서 분할정복해나가는 알고리즘
자세한 내용은 chatGPT한테 물어보면 잘 알려준다.
세 가지 종류가 있고, 자꾸 헷갈려서 정리해본다.
1. pythonic quick sort
파이썬의 특성을 살려서 간단하게 구현한 퀵소트다.
간단하게 구현해보면서 퀵소트의 대략적인 개념을 이해하기 좋다.
제자리 정렬이 아니므로 공간복잡도 측면에서 비효율적이다.
def qsort_pythonic(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left = []
right = []
mid = [pivot]
for i in arr[1:]:
if i == pivot:
mid.append(i)
elif i < pivot:
left.append(i)
else:
right.append(i)
return qsort_pythonic(left) + mid + qsort_pythonic(right)
target = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
print('before', target)
print('after', qsort_pythonic(target))2. while과 재귀함수를 활용한 퀵소트
1번보다는 발전된 형태다. 학습한 교재에서는 피벗의 인덱스를 항상 start로 고정시킨 형태로 작성되어 있었는데 피벗선택의 랜덤성을 보장하기 위해서 이렇게 개선했다.
pivot = (start + end) // 2
target[pivot], target[start] = target[start], target[pivot]
복습할 때마다 함수시그니쳐와 사용될 변수를 정확하게 기억하지 못해서 구현에 많은 어려움을 겪는다. 물론 전체 로직을 완전히 이해했다면 기억할 필요도 없겠지만 나처럼 잘 이해가 안되면 일단 외우고 이해하면 된다.
재귀함수이므로 함수 시그니쳐를 잘 기억해야 한다.
def qsort(arr, start, right)
arr : 정렬할 대상배열
start : idx 값으로 배열 원본을 변경하지 않고 인덱싱된 구간만 재귀호출한다.
end : start 와 동일. 마지막 구간이다.(일반적인 range와 달리 end도 대상에 포함)
함수 안에서 사용되는 변수
pivot : 피벗을 가리키는 인덱스, 인덱스, 인덱스, 인덱스!!! 값이 아니라 인덱스다.
left : 포인터다. 포인터를 start, end사이로 움직여서 pivot 보다 큰 값을 찾는다.
right : 오른쪽 포인터, pivot보다 작은 값을 찾는데 사용한다.
def qsort_while(target, start, end):
# 재귀에서 다루는 배열은 같은 배열임을 생각하자.
# start, end 포인터만 변경해가면서 정렬을 수행하는 것이다.
# 따라서 종료조건은 target의 length가 아니라 start와 end의 차이로 지정해야 한다.
# 여기서 start와 end는 둘다 포함되는 범위이므로 range(start, end)와 다름을 생각하자.
if start >= end:
return
pivot = (start + end) // 2 # 피벗도 인덱스로 지정한다. 인덱스와 실제 값을 헷갈리지말자
target[pivot], target[start] = target[start], target[pivot]
left = start + 1
right = end
# 두 개의 포인터가 교차하면 멈춰야 한다.
while left <= right:
# 왼쪽은 피벗보다 큰 숫자를 찾을 때 까지 계속 증가시켜준다.
while left <= end and target[left] <= target[pivot]:
left += 1
# 오른쪽은 피벗보다 작은 숫자를 찾을 때 까지 증가시킨다.
while right > start and target[right] >= target[pivot]:
right -= 1
# 만약 left와 right가 교차했다면 특수한 처리를 해줘야한다.
# right가 멈춰 선 곳에 위치한 원소는 pivot보다 작거나 같은 원소이므로
# 제일 첫 번째 원소인 pivot과 스위치해줘도 퀵정렬의 조건과 일치한다.
if left > right:
target[right], target[pivot] = target[pivot], target[right]
# 교차하지 않았다면 left, right를 바꿔주면 된다.
else:
target[left], target[right] = target[right], target[left]
# while문 안에서 피벗을 기준으로 한 정렬이 완료되었다.
# 따라서 피벗을 제외한 양 옆의 배열을 대상으로 재귀적으로 퀵정렬을 호출해준다.
# array 자체는 변화하지 않고 start, end인덱스 기준으로 퀵정렬을 수행할 구간을 지정하는 형식이므로
# 이 형식에 맞게 호출해주어야한다.
qsort_while(target, start, right - 1)
qsort_while(target, right + 1, end)
# partition 함수는 주어진 범위에서 피벗값을 기준으로 작은 값들과 큰 값들을 분리하는 역할을 수행하고, 피벗값의 위치를 반환합니다.3. partition 함수를 활용한 정석적인 구현
복습하고 추가 포스팅하러 돌아오겠다.
