학습기록 - 1 - 파이썬 - 알고리즘 - 병합정렬
병합정렬을 공부했다. 여러 알고리즘 중 복잡한 정도는 '중'이라고 생각한다.
1) 작동원리 설명
1. 전체 리스트 중 중간값을 지정한다.
2. 중간값을 기준으로 왼쪽 그룹, 오른쪽 그룹을 나눈다.
3. 그룹 리스트 수가 하나가 될 때까지(결국 하나씩 다 쪼갠다는 뜻)나눈다. 나눌 때는 수의 크기가 아니라 위치로.
ex) list = [2, 3, 1, 5, 4]
-> 1회차 = [2, 3] , [1, 5, 4] -> 중간값은 4였다.
2회차 = [2], [3], [1], [5, 4]
3회차 = [2], [3], [1], [5], [4] -> 모두 하나씩이 됐으므로 종료. 코드 설명은 아래에서.
4. 나눠진 회차 역순으로 병합 과정을 거친다. 이 때는 수를 비교해 오름차순(작은 수부터)또는 내림차순으로 정렬 후 병합한다.
나눈 결과 -> [2], [3], [1], [5], [4]
-> 1회차 = [2], [3], [1], [4, 5] -> 3회차의 마지막 나눈 과정부터 병합 진행, 새로운 리스트에 작은 수부터 정렬.
2회차 = [2, 3], [1, 4, 5] -> 2와 3인 한 세트에서 나뉜 것이고, 1, 5, 4가 한 세트에서 나뉜 것이므로.
3회차 = [1, 2, 3, 4, 5] -> 최종 병합.
2) 코드 및 코드 설명
1] divide, 나누는 단계
list = [2, 3, 1, 5, 4]
def mergesort(list): -> 함수 설정
if len(list) > 1: # 쪼개고 쪼개다가 1이 되면 아무것도 안해. 리스트 내 숫자 2개 까지는 계속 적은 수의 리스트로 divide
mid = len(list) // 2 # 리스트에 들어간 숫자들의 수를 2로 나눈 몫 -> 리스트 숫자 5개니 몫은 2다.
left_list = list[:mid] # 리스트의 mid번째 수는 0부터니까 '1'이 된다. 1을 중심으로 1 빼고 왼쪽 두개
right_list = list[mid:] # 1부터 끝까지
mergesort(left_list) #같은 방법으로 또 쪼개기, if문의 조건을 따른다.
mergesort(right_list)
2] 합치는 단계
i = 0 # i는 나눠진 왼쪽 리스트 내 수들을 대변한다.
j = 0 # j는 오른쪽.
k = 0 # k는 병합 과정에서 수를 비교해 새로운 리스트에 담기 위한 새로운 변수다.
while i < len(left_list) and j < len(right_list): # 두 조건을 만족하는 한 while 아래 코드 계속 실행.
0(1씩 커짐) < 왼쪽 리스트 내 원소 갯수 and 0(1씩 커짐) < 오른쪽 리스트 내 원소 갯수
if left_list[i] < right_list[j]: # 리스트 내 첫번째 수부터 비교. 만일 왼쪽 리스트의 첫 번째 수가 오른쪽 리스트의 값보다 작다면
list[k] = left_list[i] # 리스트도 0부터 시작이니 리스트 첫 번째 자리에 작은 수를 넣는다.
# 다 쪼개진 상태해서 비교하고, 리스트에 넣고, 한 칸씩 올라가며 재실행
i = i+1 (1씩 커짐)
k = k+1 (1씩 커짐)
else: # 만일 오른쪽 리스트의 수가 더 작다면
list[k] = right_list[j] # 오른쪽 리스트 수를 정렬할 리스트의 첫 번째 자리에 넣는다.
j = j+1 # 그리고 첫 번째 수는 넣었으니 다음 수를 체크하기 위해 +1을 한다.
k = k+1 # 여기까지 머지 # k값도 0번째는 채웠으니 1을 추가한다.
3] 합치다 보면 남는 수를 해결하기
while len(left_list) > i: # 여기는 짝수 균형 안맞아 하나 남은 것 처리. 그게 i든 j든 깍두기 정리.
a[k] = left_list[i]
i = i + 1 # 넣고 나면 +1을 해준다. 그 이유는 while 조건 성립하지 않아야 다시 위로 올라가서 다음 회차의 병합을 진행하기 때문
k = k + 1
while len(right_list) > j: # j가 남았을 때 정리하기
a[k] = right_list[j] # 이것은 오름차순 정리면 가장 큰 수일 것이고, 내림차순이면 가장 작은 수.
j = j + 1
k = k + 1
그리고는 함수에 리스트를 넣고, 프린트를 하도록 설정한다.
mergesort(list)
print("sorted list is:",list)
끝이다. while문 실행을 멈추고 다시 위로 올라가게 해줘야 한다는 점이 인상깊었다.
여러 참고 자료를 봤지만 외국 분이 만든 좋은 영상을 보고 이해할 수 있었다. 공유.
@@ 지적질과 조언과 리액션은 저를 살찌우게 합니다!