분할 정복

분할 정복이란, 복잡한 문제를 복잡하지 않은 문제로 '분할(divide)'하여 '정복(conquer)'하는 방법이다. 단 정복한 후에는 '결합(combine)'의 과정을 거쳐야 한다.

• 분할 정복 전략은 전체를 공략하는 대신, 전체를 구성하는 구성 요소들을 잘게 나누어 쪼개어진 부분을 공략한다. 이 디자인의 기본 원리는 다음과 같다.

  "8개의 데이터를 동시에 정렬하는 것보다, 이를 둘로 나눠 4개의 데이터를 정렬하는 것이 쉽고,
  
    또 이들 각각을 다시 한번 둘로 나눠서 2개의 데이터를 정렬하는 것이 더 쉽다."

• 병합 정렬과 퀵 정렬은 '분할 정복'이라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법이다.

• 두 정렬 방식은 정렬 대상을 반씩 줄여나가는 과정을 반복하게 되는데 이러한 반복은 재귀적 구현을 위한 것이다.

❗ 병합 정렬

리스트의 요소가 1개만 남을 때까지 계속 반으로 나누어 간다. 각각을 정렬한 후에, 정렬된 부분 리스트들을 합쳐 전체 리스트를 정렬하는 방식이다.

이미지 참고 사이트

<구현>

def mergeSort(ns):

    ❗ 재귀함수 탈출 구문
    if len(ns) < 2: # Item이 1개가 될 때까지
        return ns

    ❗ 분할 : 재귀함수 사용
    print('>>> Divide <<<')
    mid_idx = len(ns) // 2
    left_area = mergeSort(ns[:mid_idx])
    right_area = mergeSort(ns[mid_idx:)


    ❗ 병합
    print('>>> Merge <<<')
    sorted_area = []

    left_idx = 0; right_idx = 0
    while left_idx < len(left_area) and right_idx < len(right_area):

        if left_area[left_idx] < right_area[right_idx]:
            sorted_area.append(left_area[left_idx])
            left_idx += 1
        else:
            sorted_area.append(right_area[right_idx])
            right_idx += 1

    sorted_area += left_area[left_idx:]
    sorted_area += right_area[right_idx:]

    return sorted_area

❗ 퀵 정렬

기준(pivot) 값보다 작은 값과 큰 값으로 분리한 후 다시 합치면서 정렬하는 방식이다.

• 병합 정렬(merge sort)과 달리 퀵 정렬(Quick Sort)은 리스트를 비균등하게 분할한다.

<구현>

  def quickSort(ns, asc=True):

      if len(ns) < 2:
          return ns

      mid_idx = len(ns) // 2
      pivot = ns[mid_idx]

      smallNums = [] # pivot보다 작은 수
      sameNums = [] # pivot과 같은 수
      bigNums = [] # pivot보다 큰 수

      for n in ns:
          if n < pivot:
              smallNums.append(n)
          elif n == pivot:
              sameNums.append(n)
          else:
              bigNums.append(n)

      if asc:
          return quickSort(smallNums, asc) + sameNums + quickSort(bigNums, asc)
      else:
          return quickSort(bigNums, asc) + sameNums + quickSort(smallNums, asc)