알고리즘 3주차 - 정렬(병합 정렬)

병합 정렬

• 실제 면접에서 자주 출제됨(직접 구현 형식)

• 배열의 앞 부분과 뒷 부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업의 반복

[1, 2, 3, 5]  # 정렬된 배열 A
[4, 6, 7, 8]  # 정렬된 배열 B
[] # 두 집합을 합칠 빈 배열 C


        ↓
1단계 : [1, 2, 3, 5] 
        ↓
       [4, 6, 7, 8] 
        1과 4를 비교합니다!
        1 < 4 이므로 1을 C 에 넣습니다.
     C:[1]

           ↓
2단계 : [1, 2, 3, 5] 
        ↓
       [4, 6, 7, 8] 
        2와 4를 비교합니다!
        2 < 4 이므로 2를 C 에 넣습니다.
     C:[1, 2]


              ↓
3단계 : [1, 2, 3, 5] 
        ↓
       [4, 6, 7, 8] 
        3과 4를 비교합니다!
        3 < 4 이므로 3을 C 에 넣습니다.
     C:[1, 2, 3]

                 ↓
3단계 : [1, 2, 3, 5] 
        ↓
       [4, 6, 7, 8] 
        5와 4를 비교합니다!
        5 > 4 이므로 4을 C 에 넣습니다.
     C:[1, 2, 3, 4]

                 ↓
3단계 : [1, 2, 3, 5] 
           ↓
       [4, 6, 7, 8] 
        5와 6을 비교합니다!
        5 < 6 이므로 5을 C 에 넣습니다.
     C:[1, 2, 3, 4, 5]

엇, 이렇게 되면 A 의 모든 원소는 끝났습니다!

그러면 B에서 안 들어간 원소인
       [6, 7, 8] 은 어떡할까요?
하나씩 C 에 추가해주면 됩니다.
     C:[1, 2, 3, 4, 5, 6, 7, 8] 이렇게요!

# 출처: 스파르타코딩클럽

병합

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]

def merge(array1, array2):
    array_c = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            array_c.append(array1[array1_index])
            array1_index += 1
        else:
            array_c.append(array2[array2_index])
            array2_index += 1
    if array1_index == len(array1): # 남는걸 다 넣어주는 코드, array1이 끝났을 때
        while array2_index < len(array2):
            array_c.append(array2[array2_index])
            array2_index += 1
    if array2_index == len(array2):  # 남는걸 다 넣어주는 코드, array2이 끝났을 때
        while array1_index < len(array1):
            array_c.append(array1[array1_index])
            array1_index += 1
    return array_c

print(merge(array_a, array_b))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

병합정렬

• 위의 방법으로는 그냥 정렬된 배열을 합치는 것 즉 병합이다.

• 병합하면서 정렬을 하게 하려면 어떻게 해야할까?

  💡

  분할 정복(Divide and Conquer) - 문제를 작은 2개의 문제로 분리하고 각각 해결한 다음에 결과를 모아서 원래의 문제를 해결하는 전략 [5, 3, 2, 1, 6, 8, 7, 4] 반으로 쪼갬 [5, 3, 2, 1] [6, 8, 7, 4] 또 반으로 쪼갬 [5, 3] [2, 1] [6, 8] [7, 4] 또 반으로 쪼갬 [5] [3] [2] [1] [6] [8] [7] [4] 이 배열들을 두개씩 병합 [5] [3] > [3, 5] [2] [1] > [1, 2] [6] [8] > [6, 8] [7] [4] > [4, 7] 그러면 다시 각 배열별로 병합 [3, 5], [1, 2] > [1, 2, 3, 5] ....... [1, 2, 3, 4, 5, 6, 7, 8]

  • 이렇게 동일한 형태를 띄는 것은 "재귀적 해법"으로 풀 수 있다.
  • MergeSort(시작점, 끝점) 이라는 가정하에 MergeSort(0, N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N))
  • 부분 나눠준 후 왼쪽 부분 정렬, 오른쪽 부분 정렬, 합치면서 정렬
  • 재귀함수의 핵심은? "탈출 조건"을 정의하는 것
    • 문자열의 길이가 1보다 작거나 같을 때 탈출해야 함

  array = [5, 3, 2, 1, 6, 8, 7, 4]
  
  
  def merge_sort(array):
      if len(array) <= 1:
          return array
      mid = len(array) // 2
      left_array = merge_sort(array[:mid])
      right_array = merge_sort(array[mid:])
      return merge(left_array, right_array)
  
  
  def merge(array1, array2):
      result = []
      array1_index = 0
      array2_index = 0
      while array1_index < len(array1) and array2_index < len(array2):
          if array1[array1_index] < array2[array2_index]:
              result.append(array1[array1_index])
              array1_index += 1
          else:
              result.append(array2[array2_index])
              array2_index += 1
  
      if array1_index == len(array1):
          while array2_index < len(array2):
              result.append(array2[array2_index])
              array2_index += 1
  
      if array2_index == len(array2):
          while array1_index < len(array1):
              result.append(array1[array1_index])
              array1_index += 1
  
      return result
  
  
  print(merge_sort(array))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

  # 출력된 값을 보면 다음과 같습니다!
  # [5, 3, 2, 1, 6, 8, 7, 4]     맨 처음 array 이고,
  # left_arary [5, 3, 2, 1]      이를 반으로 자른 left_array
  # right_arary [6, 8, 7, 4]     반으로 자른 나머지가 right_array 입니다!
  
  # [5, 3, 2, 1]                 그 다음 merge_sort 함수에는 left_array 가 array 가 되었습니다!
  # left_arary [5, 3]            그리고 그 array를 반으로 자르고,
  # right_arary [2, 1]           나머지를 또 right_array 에 넣은 뒤 반복합니다.
  
  # [5, 3]
  # left_arary [5]
  # right_arary [3]
  
  # [2, 1]
  # left_arary [2]
  # right_arary [1]
  
  # [6, 8, 7, 4]
  # left_arary [6, 8]
  # right_arary [7, 4]
  
  # [6, 8]
  # left_arary [6]
  # right_arary [8]
  
  # [7, 4]
  # left_arary [7]
  # right_arary [4]
  
  # 출처: 스파르타코딩클럽

  • 시간복잡도는
    • merge 함수에서는
    • array1과 array2가 들어왔을 때 모든 인덱스를 다 볼때까지가 while문의 반복의 기준
    • array1과 array2의 길이만큼 시간복잡도가 걸림
    • O(N)
    • merge_sort 함수에서는 재귀적으로 호출되기에 생각해봐야함
    • 모든 단계에서 N만큼의 시간복잡도가 걸림
    • 처음 길이 N:
    • N/2 2개 비교하면서 합침:
    • N/4 2개 비교하면서 합침:
    • N/4 2개 비교하면서 합침
    • ... k 단계까지 :
    • N/2^k = 1 → k = log2N
    • 즉 k단계만큼 반복하는데 각각 단계는 O(N) 만큼의 시간복잡도를 가진다.
    • log2N * O(N) = O(NlogN)