목차
정렬이란?
- 임의로 나열되어 있는 데이터들을 주어진 항목에 따라 크기 순서대로 작은 순서부터 (오름차순) 또는 큰 순서부터 (내림차순) 늘어놓은 것임
- 정렬되어 있는 데이터들은 다음과 같은 작업을 수행할 때 응용
① 데이터를 탐색할 때
② 리스트에 있는 다른 항목들을 비교할 때
분할 정복 Divide and Conquer
more learn
분할 정복은 말 그대로 문제를 ‘분할’ 해서 ‘정복’ 한 다음 정답을 ‘조합’해 나간다는 의미
- 분할 정복은 재귀를 활용하는 대표적인 알고리즘
퀵 정렬
- 가장 유명한 정렬 알고리즘
- 피벗을 기준으로 좌우를 나누는 특징 때문에 파티션 교환 정렬 Partition-Exchange Sort 이라고도 불림
-
데이터를 비균등하게 분할한 후 반복 정렬
① 데이터에서 기준(pivot) 설정
② Pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽 분할
③ Pivot을 기준으로 왼쪽과 오른쪽을 재귀적으로 반복.
④ 정렬된 부분 배열을 하나의 배열에 병합 - 모든 정렬 방법 중에서 평균 수행 시간이 가장 빠른 방법
- 현재 정렬 과정에서 처리되고 있는 피벗 키 p 를 기준으로 원소를 두 부분으로 나눔
- 나누어진 두 부분을 따로 다시 퀵 정렬을 수행하여 모든 원소가 순서대로 정렬될 때까지 실행
Lomuto Partition Scheme
여러 가지 변형과 개선 버전이 있는데 가장 대표적인 Lomuto 의 파티션 계획 Lomuto Partition Scheme 을 구현해보겠음
- 항상 맨 오른쪽의 피벗을 택함
- 매우 기본이고 간단한 퀵정렬의 방법
- 피벗보다 작은 값을 left값으로 옮김
[구현 순서]
① 오른쪽 right 포인터가 이동하면서
- 피벗의 값 > right 포인터 값: right 포인터 값과 left 포인터 값 스왑
② 스왑 이후에는 왼쪽 left 포인터가 함께 이동
③ 오른쪽 포인터가 끝에 도달하게 되면
- 피벗 미만인 값: 왼쪽 위치
- 피벗 이상인 값: 오른쪽 위치
④ 왼쪽 포인터의 위치로 피벗 아이템이 이동
- 피벗을 기준으로 작은 값은 왼쪽에 큰 값은 오른쪽으로 분할됨
- 피벗이 그 중앙에 위치
⑤ ①~④ 반복
- 이렇게 계속 분할하면서 lo < hi 를 만족하지 않을 때까지(서로 위치가 역전할 때까지) 계속 재귀로 반복
[포인터]
- left: 피벗보다 작으면 +1(if)
- right: 탐색해가면서 피벗과 값 비교(for)
수도코드
파티션을 나누고 각각 재귀 호출(분할)
Quicksort(A, lo, hi)
if lo < hi
pivot := partition(A, lo, hi)
Quicksort(A, lo, pivot - 1)
Quicksort(A, pivot + 1, hi)
피벗: 맨 오른쪽 값을 기준
- 피벗을 기준으로 2개의 포인터가 이동
- 오른쪽 포인터의 값 < 피벗 : 스왑
partition(A, lo, hi)
pivot := A[hi]
i := lo
for j := lo to hi do
if A[j] < pivot then
swap A[i] with A[j]
i := i + 1
swap A[i] with A[hi]
return i
시간 복잡도
- 평균 수행 시간: O(\(nlog_{2}n\))
- 정렬해야 할 원소들의 값에 따라 최악의 경우에는 O(\(n^2\))
[최선의 경우]
[최악의 경우]
평가
- 모든 정렬 방법 중에서 평균 수행 시간이 가장 빠른 방법
구현
파이썬
1) pivot, left값 정리
2) for문르도 right값 설정
2.1) 피벗과 비교(피벗보다 작은 값 찾기)
2.1.1) 바꾸기
2.1.2) left값 늘리기
def quicksort(A, lo, hi):
def partition(lo, hi):
pivot = A[hi]
left = lo
for right in range(lo, hi):
if A[right] < pivot:
A[left], A[right] = A[right], A[left]
left += 1
# pivot = A[hi]니까 피벗의 자리를 옮기는 것
A[left], A[hi] = A[hi], A[left]
return left
if lo < hi:
pivot = partition(lo, hi)
quicksort(A, lo, pivot - 1)
quicksort(A, pivot + 1, hi)