1. 알고리즘 관련 공부
이번 주는 공부했던 알고리즘 지식을 정리하려 한다.
병합 정렬
- 분할 정복 알고리즘 중 하나, 이분 탐색과 같은 투 포인터 전략을 사용
- mid point를 찾아서 두 파트로 분할한다. mid = (lt+rt)//2
- dfs와 같이 트리를 이용하는데 이진트리로 계속 정렬할 리스트를 나누는 것이다.
- 기본적인 구성은 recursion 함수이다.
- 특징은 분할 정복을 사용하기 때문에 두 파트로 나뉜다는 것이다.
- 첫번째 파트는 분할이다. recursion의 특징을 이용하여 왼쪽 파트, 오른쪽 파트로 나눈다.
- 두 번째 파트는 정복이다. 여기서는 함수 본연의 코드라고 보면 된다.
- 리스트는 콜 바이 레퍼런스가 되므로 temp라는 빈 리스트를 만들어 양 쪽 파트의 값들을 비교하면서 넣는다.
- 여기서 만일 한 파트의 값들이 비교가 끝난 채로 남았다면 temp에 다 넣는다.
- temp의 값들을 진짜 리스트에 넣는다. 단 0부터 넣는게 아니라 lt 즉, 왼쪽 포인터 부터 넣어야된다.
# 이분 탐색의 연장선
# 병합정렬, 왼쪽 인덱스와 오른쪽 인덱스
# 어레이1과 어레이2가 끊임없이 비교하는 거다.
def Dsort(lt,rt):
if lt < rt:
# 중간 값 찾기
mid = (lt + rt)//2
# 두 갈래로 뻗어 나누어진다.
Dsort(lt,mid)
Dsort(mid,rt)
# ========================== 여기까지 분할, 이 아래는 정복
# 이게 가능한 이유는 리스트의 콜 바이 레퍼런스 때문이다.
# merge
# 본연의 일 코딩
# - 여기가 merge 코드다.
# 2분할한 왼쪽 자식
p1 = lt
# 2분할한 오른쪽 자식
p2 = mid + 1
# 임시 리스트 생성
temp = []
# 자식들이 한 바퀴 돌 때까지
# 어느 한 쪽이 다 돌면 멈춰야한다.
while p1 <= mid and p2 <= rt:
if arr[p1] < arr[p2]:
temp.append(arr[p1])
p1+=1
elif arr[p1] > arr[p2]:
temp.append(arr[p2])
p2+=1
# p1이 남았다.
if p1<=mid: # 남은 것들 다 넣자 mid 포함
temp = temp + arr[p1:mid+1]
# p2 남았다.
if p2<=lt: # 남은 것들 다 넣자 lt 포함
temp = temp + arr[p2:lt+1]
# 정렬된 temp를 넘겨주어야한다.
for i in range(len(temp)):
# 조심 그냥 i에 넣어버리면 0으로 들어간다.
# lt에 i를 더한 인덱스를 넣어주자
# 다시 arr에 복사
arr[lt + i] = temp[i]
if __name__ == "__main__":
arr = [23,11,45,36,15,67,33,21]
print("Before sort : ", end = "")
print(arr)
Dsort(0,7)
print()
print("After sort : ", end = "")
print(arr)
퀵 정렬
- 불안정 정렬이자, 비교 정렬, 퀵 정렬도 병합 정렬과 비슷하게 분할을 사용하지만 비균등 분할을 한다.
- 병합 정렬과 똑같이 투 포인터 전략을 쓴다. lt와 rt
- 병합 정렬은 선위 순회 방식(선 분할, 후 정렬)이지만 퀵 정렬은 후위 순회 방식(선 정렬, 후 분할)이다.
- 피벗을 정하고 피벗을 기준으로 파티션을 만든다. 피벗은 보통 rt로 정한다.
- 버블 정렬과 같이 for문을 통해 한 번 돌 때 정렬을 한 번 돌고 다음 파트로 나뉘어 넘어가서 정렬한다.
- 본 함수의 로직이 끝나면 그 다음에 분할을 시작한다.
- 스왑 로직은 pos라는 lt 부터 출발하는 추가 포인터가 필요하다.
- 정렬을 돌 때 현재 위치의 값과 피벗을 비교해서 피벗 값이 연해 위치의 값보다 크면 pos값과 스왑하고 pos에 +1 한다.
- for문이 끝나면 pos의 값과 피벗을 스왑한다.
- 위 로직이 본 함수의 로직으로서 끝난다면 분할을 한다. 분할 기분은 pos로 lt부터 pos -1, pos+1부터 rt로 pos는 고정한다.
# 퀵정렬
# 병합 정렬은 선위 순회 방식
# 퀵정렬은 후위 순회 방식
# 병합 정렬은 먼저 나누고 그 다음 정렬
# 퀵정렬은 정렬하고 나눔
# 파티션 => 중심 값을 가지고 왼쪽과 오른쪽을 나눈다. == 분할
# 즉 병합정렬 => 선 파티션, 후 정렬
# 퀵정렬 => 선 정렬, 후 파티션
# 퀵정렬 또한 병합정렬과 같이 분할해서 생각한다.
# 퀵정렬은 피벗값을 지정해야한다. 피벗을 결정하는 데에 있어 성능 차이가 난다.
# 요새는 맨 오른쪽 값을 가장 많이 쓴다.
# 피벗값 == 중심값
# 피벗 값을 정하고 파티션을 진행
# pivot = arr[rt]
def QSort(lt, rt):
if lt < rt:
# lt 부터 rt 전까지
pos = lt # pos 정하기, pos는 인덱스다.
pivot = arr[rt] # pivot 정하기, pivot은 값이다.
for i in range(lt,rt):
# pivot 값과 arr[i]를 비교해서
# 정렬을 시작한다. pivot 값이 arr[i]보다 크면
# arr[pos]와 arr[i]의 값을 스왑
# 스왑이 진행됐다면 pos에 1을 더해 인덱스를 증가시킨다.
# pivot 값과 arr[i]를 다시 비교한다.
if arr[i] <= pivot:
temp = arr[i]
arr[i] = arr[pos]
arr[pos] = temp
pos+=1
# for문이 끝나면 arr[pos]와 pivot의 값을 스왑한다.
temp = arr[pos]
arr[pos] = pivot
arr[rt] = temp
# 이 다음에 분할! 재귀를 쓰자
# DFS => 상태트리, 분할정렬은 => 분할 단계
# pos는 가운데 기준이므로 포함하지 말자
# 이미 기준을 세워서 나눴기 때문이다.
QSort(lt, pos - 1)
QSort(pos+1, rt)
if __name__ == "__main__":
arr = [45, 21, 23, 36, 15, 67, 11, 60, 20, 33]
print("Befoe sort : ", end = '')
print(arr)
# 처음 인덱스 부터 끝 인덱스까지 정렬
QSort(0, len(arr)-1)
print("After sort : ", end = '')
print(arr)
