<aside> 🔥 분할 정복으로 배열을 정렬하는 알고리즘
여러가지 변형과 개선 버전이 있는데 로무토가 구현한 파티션 계획을 알아보았다.
항상 맨 오른쪽의 피벗을 택하는 단순한 방식이다.
이를 기준으로 2개의 포인터가 이동해서 오른쪽 포인터의 값이 피벗보다 작으면 서로 스왑하는 형태.
</aside>
[1, 6, 2, 9, 4] # 정렬되지 않은 배열
1단계: [1, 6, 2, 9, 4]
마지막 원소인 4를 pivot으로 삼습니다.
pivot보다 작은 집합의 인덱스 i를 -1로 설정합니다.
(i=-1)
2단계: [1, 6, 2, 9, 4]
j를 0에서부터 3까지 살펴봅니다.
j가 0이므로 지금 살펴보고 있는 값은 1 입니다.
1는 pivot(4)보다 작습니다.
i를 1 증가시켜 0으로 만듭니다.
i 와 j 의 위치를 바꿉니다.
i와 j가 동일하므로 아무 일도 일어나지 않습니다.
(i=0, j=0)
3단계: [1, 6, 2, 9, 4]
j를 1 증가시켜 1로 만듭니다.
지금 살펴보고 있는 값은 6 입니다.
6은 pivot(4)보다 큽니다.
넘어갑니다.
(i=0, j=1)
4단계: [1, 6, 2, 9, 4]
j를 1 증가시켜 2로 만듭니다.
지금 살펴보고 있는 값은 2 입니다.
2는 pivot(4)보다 작습니다.
i를 1 증가시켜 1로 만듭니다.
i(1) 와 j(2) 의 위치를 바꿉니다.
배열은 [1, 2, 6, 9, 4]가 됩니다.
(i=0, j=2)
5단계: [1, 2, 6, 9, 4]
j를 1 증가시켜 3으로 만듭니다.
지금 살펴보고 있는 값은 9 입니다.
9는 pivot(4)보다 큽니다.
넘어갑니다.
(i=1, j=3)
6단계: j를 0부터 3까지 모두 살펴보았습니다.
i는 pivot보다 작은 집합의 범위를 나타내므로, i+1과 pivot의 위치를 바꿉니다.
배열은 [1, 2, 4, 9, 6] 이 됩니다.
7단계: [1, 2]와 [9, 6]을 대상으로 1~6단계를 반복합니다.
결과적으로 [1, 2, 4, 6, 9]가 됩니다.
정렬이 끝났습니다.
퀵 정렬 구현
def quicksort(list, start, end):
# 파티션 정렬하기
def partition(part, ps, pe):
# 피봇을 맨 끝으로
pivot = part[pe]
# i = 시작점 - 1
i = ps - 1
# 시작부터 끝까지 반복
for j in range(ps, pe):
# 피봇보다 j가 작을 경우
if part[j] <= pivot:
# i + 1 해주고 자리 변경
i += 1
part[i], part[j] = part[j], part[i]
# 작은 부분 / 피봇 / 큰 부분 으로 정렬
part[i + 1], part[pe] = part[pe], part[i + 1]
return i + 1
# 시작점이 끝점보다 커지면 종료
if start >= end:
return None
# 파티션 정렬
p = partition(list, start, end)
# 재귀적으로 다시 정렬
quicksort(list, start, p - 1)
quicksort(list, p + 1, end)
return list
print(quicksort([4, 6, 2, 9, 1], 0, 4))
퀵소트의 시간복잡도
<aside> 🔥 최악의 경우에는 O(N**2)이 된다.
만약 이미 정렬된 배열이 입력값으로 들어오면 피벗은 계속 오른쪽에 위치하기 때문에
최악의 성능을 보여준다.
</aside>