학습기록 - 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문 실행을 멈추고 다시 위로 올라가게 해줘야 한다는 점이 인상깊었다. 

여러 참고 자료를 봤지만 외국 분이 만든 좋은 영상을 보고 이해할 수 있었다. 공유.

 

youtu.be/_EPZCbjdqTk

 

@@ 지적질과 조언과 리액션은 저를 살찌우게 합니다!