def bubblesort(A):
# (1)
for i in range(1, len(A)):
# (2)
for j in range(0, len(a)-i):
# (3)
if A[j] > A[j+1]:
A[j], A[j+1] = A[j+1], A[j]
# (1) 2개씩 비교하니까 n-1번 수행
# (2) 0부터 매 루프마다 i개씩 뺀 범위에서 비교 수행
# (3) 앞 요소가 더 크면 두 요소의 자리를 바꿈
병합 정렬
분할정복 방식의 정렬로, 데이터를 쪼개서 정렬하고 합쳐서 다시 정렬하는 방식
시간복잡도가 최악/최선 모두 O(n log n) -> 사실상 완전한 Θ(n log n)
안정 정렬(Stable Sort)
def mergesort(A):
def merge(left, right):
result = []
# (4)
l = r = 0
while l < len(left) or r < len(right):
# (5)
if l == len(left):
result.append(right[r])
r += 1
elif r == len(right):
result.append(left[l])
l += 1
# (6)
elif left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
return result
# (1)
if len(A) < 2:
return A
# (2)
left = mergesort(A[:len(A) // 2])
right = mergesort(A[len(A) // 2:])
# (3)
return merge(left, right)
# (1) 배열의 길이가 2보다 작으면 그대로 반환
# (2) 배열을 left/right로 각각 재귀
# (3) left/right에 대해 merge 수행하여 반환
# (4) [merge] left/right를 0부터 끝까지 탐색
# (5) [merge] left/right 중 하나의 배열만 남으면 그대로 붙이기
# (6) [merge] left/right 중 작은 값을 결과에 push
퀵정렬
임의의 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누어 정렬하는 알고리즘
파티션 교환 정렬 (Partition-Exchange Sort)라고도 불림
로무토 파티션 - 항상 맨 오른쪽 피벗을 선택하는 방식
def quicksort(A, lo, hi):
def partition(lo, hi):
# (4)
pivot = A[hi]
# (5)
left = lo
for right in range(lo, hi):
# (6)
if A[right] < pivot:
A[left], A[right] = A[right], A[left]
left += 1
# (7)
A[hi], A[left] = A[left], A[hi]
return left
# (1)
if lo < hi:
# (2)
pivot = partition(lo, hi)
quicksort(A, lo, pivot-1)
quicksort(A, pivot+1, hi)
# (1) 비교할 데이터가 있으면
# (2) partition : pivot을 뽑아 left/right로 나눔
# (3) left/right에 각각 재귀
# (4) [partition] 로무토 파티션 : 가장 오른쪽 요소를 pivot으로 선택
# (5) [partition] right를 lo부터 hi전까지 탐색
# (6) [partition] right가 pivot보다 작으면 left와 교환 후 left 증가
# (7) [partition] left와 pivot 교환
안전 정렬 vs 불안정 정렬
안정 정렬 - 정렬 과정에서 중복된 값들(비교하는 값이 같은 요소들)에 대한 순서가 입력 순서와 동일하게 정렬함
