병합 정렬 쉽게 배우기: 재귀 호출과 병합 과정을 시각적으로 따라가기

병합 정렬(Marge Sort)은 분할 정복 알고리즘에 기반한 정렬 알고리즘 중 하나로, 안정적이고 효율적인 정렬 방식입니다.

이번 포스트에서는 앞에서 병합 정렬 코드에 대해 알아보고 뒤에서는 병합 정렬을 시각화한 글을 보고 병합 과정을 따라가 볼 것입니다.

 

일단 병합 정렬의 핵심 3가지를 알아보겠습니다.

1. 분할(Divide)
   1. 배열(또는 리스트)을 절반씩 나눕니다.
   2. 나누는 과정을 재귀적으로 반복하여, 크기가 1인 배열로 쪼갭니다.
      1. 크기가 1인 배열은 이미 정렬된 상태라고 가정합니다.
2. 정복(Conquer)
   1. 작은 두 배열을 비교하면서 정렬하여 병합(Marge)합니다.
   2. 병합 과정에서 두 배열을 한 번에 순회하며, 각 리스트의 첫 번째 요소를 비교하여 더 작은 값을 새로운 리스트에 추가하는 방식으로 진행합니다.
3. 병합(Merge)
   1. 두 개의 정렬된 배열을 하나의 정렬된 배열로 병합(Marge)합니다.
   2. 이를 통해 마지막 단계에서 정렬된 배열을 얻습니다.

---

병합 정렬의 기본 구현을 알아보겠습니다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

# 예시 입력
unsorted_list = [3, 7, 1, 4, 1, 5]
sorted_list = merge_sort(unsorted_list)
print(sorted_list)	#[1, 1, 3, 4, 5, 7]

 

코드를 분석해 보겠습니다.

1. marge_sort() 함수
   이 함수는 재귀적으로 배열을 나누고, 병합하여 정렬하는 병합 정렬의 핵심입니다.
   
   1. 기저 조건:

      if len(arr) <= 1:
          return arr

       배열의 길이가 1 이하라면 이미 정렬된 상태로 간주하고 그대로 반환합니다.
      
      
   2. 배열 분할:

      mid = len(arr) // 2
      left_half = merge_sort(arr[:mid])
      right_half = merge_sort(arr[mid:])

      배열의 중간 인덱스 mid를 기준으로 두 부분으로 나눕니다. arr[:mid]는 왼쪽 절반, arr[mid:]는 오른쪽 절반을 의미합니다.
      이 과정을 재귀적으로 호출하여 단일 원소로 나눌 때까지 반복합니다.
      
      
   3. 병합:

      return merge(left_half, right_half)

      나뉜 두 부분을 marge() 함수로 병합하며 정렬합니다.
      
      
2. marge() 함수
   이 함수는 두 개의 정렬된 리스트를 병합하여 하나의 정렬된 리스트를 반환합니다.
   
   1. 병합 과정:

      while i < len(left) and j < len(right):
          if left[i] < right[j]:
              sorted_array.append(left[i])
              i += 1
          else:
              sorted_array.append(right[j])
              j += 1

       두 리스트 left, right의 첫 번째 요소를 비교하며 더 작은 값을 sorted_array에 append 합니다.
      비교 후에 해당 리스트의 인덱스를 증가시킵니다.
      
      
   2. 남은 요소 처리:

      sorted_array.extend(left[i:])
      sorted_array.extend(right[j:])

       한쪽 리스트의 요소가 모두 출력되었을 경우, 다른 쪽 리스트에 남아 있는 요소들을 결과 리스트에 추가합니다.

 

---

병합 정렬(Merge Sort)은 컴퓨터 과학에서 가장 중요한 정렬 알고리즘 중 하나로, 효율성과 안정성을 모두 갖춘 강력한 알고리즘입니다만, 재귀 호출과 병합 과정이 반복적으로 이루어지기 때문에 다소 어렵게 느껴질 수 있습니다.

이에 따라, 병합 정렬의 과정을 단계별로 상세히 설명하며, 각 단계에서 어떤 일이 일어나는지 번호 체계와 기호를 통해 시각적으로 표현하고자 했습니다. 이를 통해 독자들이 위의 코드를 보고 이해하기 어려웠다면, 글을 읽으면서 병합 정렬의 동작 원리를 쉽게 따라갈 수 있도록 돕고자 했습니다..

병합 정렬의 과정을 단계적으로 표현하기 위해 아래와 같은 기호와 들여 쓰기 규칙을 사용했습니다. 사실

1. 번호 체계
   • '깊이-활동 순서' 형식으로 번호를 매겼습니다.
     • 첫 번째 숫자: 재귀 호출의 깊이를 나타냅니다.
       1. 예: 0-1은 깊이 0(최상위 호출)을 의미합니다.
       2. 깊이가 증가할수록 더 작은 리스트를 처리하는 단계입니다.
     • 두 번째 숫자: 해당 깊이에서의 활동 순서를 나타냅니다.
       1. 예: 1-1은 깊이 1에서 첫 번째 활동(왼쪽 리스트 처리)을 의미합니다.
2. 들여 쓰기
   • 들여 쓰기는 재귀 호출의 깊이를 시각적으로 표현합니다.
     • 들여 쓰기가 깊어질수록 더 작은 리스트를 처리하는 단계입니다.
     • 예: 1-1은 0-1보다 한 단계 더 깊은 재귀 호출을 나타냅니다.
3. 주요 기호
   • return [x]: 리스트가 길이가 1이 되어 반환되는 시점입니다.
   • end: 현재 활동(재귀 호출 또는 병합)이 종료되는 시점입니다.
   • Merging [A] and [B]: 두 리스트 [A]와 [B]가 병합되는 과정을 나타냅니다. marge() 함수 속입니다.
   • result.append(x): 병합 과정에서 결과 리스트에 요소를 추가하는 단계입니다.
   • result.extend(right[j:]): 병합 과정에서 한쪽 리스트의 남은 요소를 결과 리스트에 추가하는 단계입니다.

 

---

아래는 시각화한 병합 정렬 과정입니다.

 

0-1: merge_sort([3, 7, 1])  # 깊이 0, 전체 리스트 처리
    1-1: left = merge_sort([3])  # 깊이 1, 왼쪽 리스트 처리
        2-1: return [3]  # 깊이 2, 리스트 길이가 1이므로 반환
        2-1: end
    1-1: left = [3]
    1-1: right = merge_sort([7, 1])  # 깊이 1, 오른쪽 리스트 처리
        2-2: left = merge_sort([7])  # 깊이 2, 왼쪽 리스트 처리
            3-1: return [7]  # 깊이 3, 리스트 길이가 1이므로 반환
            3-1: end
        2-2: left = [7]
        2-2: right = merge_sort([1])  # 깊이 2, 오른쪽 리스트 처리
            3-2: return [1]  # 깊이 3, 리스트 길이가 1이므로 반환
            3-2: end
        2-2: right = [1]
        2-2: return merge([7], [1]) #merge() 함수로 들어갑니다.
            Merging [7] and [1] -> result: [1,7]
        2-2: result = [1,7] #merge() 함수의 반환값입니다.
        2-2: end
    1-1: right = [1,7]
    1-2: return merge([3], [1,7]) # 최종 병합 수행
        Merging [3] and [1,7]:
            result.append(1) -> result = [1]
            i = 0, j = 1
            result.append(3) -> result = [1,3]
            i = 1, j = 1
            반복문 종료
            result.extend(right[j:]) -> result = [1,3,7] (right[j:] = [7])
        marge([3], [1,7]) -> result: [1,3,7]
    1-2: end
0-1: end

 

 

 

 

---

 

# 이 글의 내용 중 일부는 Perplexity AI의 도움을 받아 정보를 수집하고 정리하였으며, 추가적인 연구와 개인적인 견해를 더하였습니다.