August 13, 2021
코드로 구현하면 다음과 같다.
def bubblesort(A):
for i in range(1, len(A)):
for j in range(0, len(A) - 1):
if A[j] > a[j + 1]:
A[j], A[j + 1] = a[j + 1], A[j]
💡 위 예시의 분할 정복 과정 설명
[7, 3, 2, 16, 24, 4, 11, 9]
인 입력값의 절반을 분리 하여[7, 3, 2, 16]
과[24, 4, 11, 9]
로 분리- 다시 이 분할된 값을 절반으로 분리
[7, 3]
,[2, 16]
,[24, 4]
,[11, 9]
- 이런식으로 더이상 쪼갤수 없을때 까지 부할 한 후 분할이 끝나면 정렬하면서 병합한다. (
[7]
,[3]
→[3, 7]
)
pivot
을 기준으로 좌우를 나누는 특징 때문에 파티션 교환 정렬(Partition-Exchange Sort)라고도 불린다.퀵 정렬은 여러가지 변형과 개선 버전이 있는데 이중 N. Lomuto의 파티션 계획을 코드로 구현하면 다음과 같다.
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
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)
이를 기준으로 2개의 포인터가 이동해서 오른쪽 포인터가 읪이 피벗보다 작다면 서로 스왑하는 형태로 진행한다. 이를 그림으로 표현하면 다음과 같다.
right
포인터가 이동하면서 피벗의 값이 오른쪽 값보다 더 클때 왼쪽과 오른쪽의 스왑이 발생한다.left
)포인터가 함께 이동한다.lo < hi
를 만족하지 않을때 까지, 즉 서로 위치가 역전할 때 까지 계속 재귀로 반복되면서 정렬이 완료된다.