2019.07.04 TIL
(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)
# 질문에 답하기
정렬 O(nlogn) - 자료의 구조가 많아 질수록 정렬의 효율이 높아진다.
- 퀵소트
- 머지소트
1. 퀵소트
- 하나의 스택프레임 안에서 conquer를 한 이후에 다시 호출 할 때 divide가 되는 것이다.
- 파티션을 알고 있으면 좋다.
- 피벗을 기준으로 왼쪽에는 작은 값이, 큰 값은 오른쪽에 오도록 몰아버리는 것
- conquer이다.
- pivot은 인덱스가 아니라 값이다.(처음 혹은 끝, 중간)
- 재귀 함수 사용
def quick_sort(arr, start, end):
#기저조건(base case)
if start >= end:
return
left = start
right = end
pivot = arr[(left+right)//2] #정수형 나누기 해야됨
#파티션
#left와 right가 교차하기 전이라면 파티션을 계속 수행한다.
while left <= right:
#left가 언제 멈춰야 하나?
while arr[left]<pivot:
left+=1
#right가 언제 멈춰야 하나?
while arr[right]>pivot:
right-=1
# left와 right가 교차하지 않았다면 교환
if left <= right:
arr[left], arr[right] = arr[right], arr[left]
left+=1
right-=1
quick_sort(arr, start, right)
quick_sort(arr, left, end)
if __name__ == "__main__":
arr = [7, 2, 5, 12, 6, 10, 8, 1, 3]
start = 0
end = 7
quick_sort(arr, start, len(arr)-1)
print(arr)
2. 머지소트
- 먼저 다 나누고 정렬을 한다.
- 하나 하나가 다 스택프레임으로 쌓인다.
- 다 나눈 이후에 왼쪽은 left 오른쪽은 right
def merge(arr, start, mid, end):
left = start
right = mid + 1
temp = [] #로컬 베리어블이라서 업데이트 안하면 사라져버린다.
# 둘 중에 하나라도 범위를 벗어나기 전가지
while left<= mid and right <= end:
if arr[left] <= arr[right]:
temp.append(arr[left])
left += 1
else:
temp.append(arr[right])
right += 1
#만약에 남아있는 것이 right라면
#right를 돌면서 temp에에 넣는다.
while right <= end:
temp.append(arr[right])
right +=1
while left <= mid:
temp.append(arr[left])
left += 1
# arr에 temp를 업데이트 하는 코드
arr[start:end+1] = temp
print(temp)
def merge_sort(arr, start, end):
#base_case
if start >= end:
return
mid = (start+end)//2
#divide
merge_sort(arr, start, mid)
merge_sort(arr, mid+1, end)
#conquer
merge(arr, start, mid, end)
if __name__ == "__main__":
arr = [3,6,9,1,3,5,7,8]
start = 0
end = len(arr)-1
merge_sort(arr, start, end)
print(str(arr))