파이썬과 컴퓨터 사이언스(알고리즘) - 병합 정렬 (merge sort)

8. 병합 정렬 (merge sort)

  • 재귀용법을 활용한 정렬 알고리즘
    1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
    2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
    3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

어떻게 코드로 만들까?

  • 데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)
    • 예: data_list = [1, 9, 3, 2]
      • 먼저 [1, 9], [3, 2] 로 나누고
      • 다시 앞 부분은 [1], [9] 로 나누고
      • 다시 정렬해서 합친다. [1, 9]
      • 다음 [3, 2] 는 [3], [2] 로 나누고
      • 다시 정렬해서 합친다 [2, 3]
      • 이제 [1, 9] 와 [2, 3]을 합친다.
        • 1 < 2 이니 [1]
        • 9 > 2 이니 [1, 2]
        • 9 > 3 이니 [1, 2, 3]
        • 9 밖에 없으니, [1, 2, 3, 9]

알고리즘 생각해보기

  • mergesplit 함수 만들기

    • 만약 리스트 갯수가 한개이면 해당 값 리턴
    • 그렇지 않으면, 리스트를 앞뒤, 두 개로 나누기
    • left = mergesplit(앞)
    • right = mergesplit(뒤)
    • merge(left, right)
  • merge 함수 만들기

    • 리스트 변수 하나 만들기 (sorted)
    • left_index, right_index = 0
    • while left_index < len(left) or right_index < len(right):
      • 만약 left_index 나 right_index 가 이미 left 또는 right 리스트를 다 순회했다면, 그 반대쪽 데이터를 그대로 넣고, 해당 인덱스 1 증가
      • if left[left_index] < right[right_index]:
        • sorted.append(left[left_index])
        • left_index += 1
      • else:
        • sorted.append(right[right_index])
        • right_index += 1

알고리즘 작성전, 리스트 앞뒤, 두 개로 나누기는 어떻게 할까?

  • 당황하지 않기, 테스트 해보면 됨, 테스트를 수백번 해도 뭐라할 사람은 없음
  • 코드를 한번 생각해보고, 다음과 같이 테스트를 먼저 합니다.
In [ ]:
int(3 / 2)
In [ ]:
split = 4 // 2
In [ ]:
data_list = [1, 2, 3, 4]
In [ ]:
data_list[:split]
In [ ]:
data_list[split:]


In [ ]:
data_list = [1, 2, 3, 4]
data_list[:2]
In [ ]:
data_list[2:]

작은 부분부터 작성해서 하나씩 해결해갑니다.

프로그래밍 연습
어떤 데이터리스트가 있을 때 리스트를 앞뒤로 짜르는 코드 작성해보기 (일반화)
In [ ]:
def split_func(data_list):
    medium = len(data_list) // 2 
    print (data_list[:medium])
    print (data_list[medium:])    
In [ ]:
data_list = [1, 2, 3, 4, 5]
In [ ]:
split_func(data_list)

이렇게 만들어보기 (재귀용법 활용)



In [ ]:
def mergesplit(data_list):
    if len(data_list) <= 1:
        return data_list
    
    medium = len(data_list) // 2
    left = mergesplit(data_list[:medium])
    right = mergesplit(data_list[medium:])    
    return merge(left, right)

프로그래밍 연습

다음 문장을 코드로 작성해보기 (merge함수는 아직은 없는 상태, 있다고만 가정)
* mergesplit 함수 만들기
  - 만약 리스트 갯수가 한개이면 해당 값 리턴
  - 그렇지 않으면, 리스트를 앞뒤, 두 개로 나누기
  - left = mergesplit(앞)
  - right = mergesplit(뒤)
  - merge(left, right)
In [ ]:
def mergesplit(data_list):
    if len(data_list) == 1:
        return data_list
    medium = int(len(data_list) / 2)
    left = mergesplit(data_list[:medium])
    right = mergesplit(data_list[medium:])
    return merge(left, right)

merge 함수 만들기

  • 목표: left 와 right 의 리스트 데이터를 정렬해서 sorted_list 라는 이름으로 return 하기
  • left와 right는 이미 정렬된 상태 또는 데이터가 하나임

프로그래밍 연습
  1. left 부터 하나씩 right과 비교
  2. left > right 이면, left 를 sorted_list에 넣고, 다음 left 리스트와 right 비교
    • 그렇지않으면 반대로 하기
      다음 경우만 프로그래밍으로 작성해보기
      left = [0]
      right = [3]
      결과는 별도의 리스트 변수를 만들어 적은 숫자 순으로 순서대로 저장해서 리턴
      

프로그래밍 연습

다음 경우만 프로그래밍으로 작성해보기
left = [0, 2]
right = [1]
결과는 별도의 리스트 변수를 만들어 적은 숫자 순으로 순서대로 저장해서 리턴

프로그래밍 연습

다음 경우만 프로그래밍으로 작성해보기
left = [0, 2]
right = [1, 3]
결과는 별도의 리스트 변수를 만들어 적은 숫자 순으로 순서대로 저장해서 리턴

프로그래밍 연습
left, right 리스트 변수의 데이터 수가 한 개에서 여러 개가 될 수 있을때 작성해보기(일반화)

1. sorted_list 리스트 변수 선언하기
2. left_index, right_index 를 0 으로 초기화 하기
3. while left_index < len(left) or right_index < len(right) 이면,
   - 만약 left_index >= len(left)이면, sorted_list 에 right[right_index] 를 추가하고, right_index 값을 1증가
   - 만약 right_index >= len(right)이면, sorted_list 에 left[left_index] 를 추가하고, left_index 값을 1증가
   - 만약 left[left_index] < right[right_index]이면, sorted_list 에 left[left_index] 를 추가하고, left_index 값을 1증가
   - 위 세가지가 아니면, sorted_list 에 right[right_index] 를 추가하고, right_index 값을 1증가


In [ ]:
# merge 함수
def merge(left, right):
    sorted_list = list()
    left_index, right_index = 0, 0   # 여러 변수를 한 줄에 써도 됨, 내부적으로는 튜플과 동일하게, 각 값이 순서대로 입력됨
    # print ("data", len(left), len(right))         # 헷깔리면, 내부 로직에서 변수가 변하는 바를 직접 출력해봅니다.
    while left_index < len(left) or right_index < len(right):
        # print (left_index, right_index)           # 헷깔리면, 내부 로직에서 변수가 변하는 바를 직접 출력해봅니다.
        if left_index >= len(left):
            sorted_list.append(right[right_index])
            right_index += 1
        elif right_index >= len(right):
            sorted_list.append(left[left_index])
            left_index += 1
        elif left[left_index] < right[right_index]:
            sorted_list.append(left[left_index])
            left_index += 1
        else:
            sorted_list.append(right[right_index])
            right_index += 1
    # print (sorted)
    return sorted_list
In [ ]:
# 데이터 준비: data_list 10개 만들기
import random 
data_list = random.sample(range(100), 10)
In [ ]:
data_list
In [ ]:
mergesplit(data_list)

살짝 다르게 구현한 코드

In [ ]:
import random 
data_list = random.sample(range(100), 10)
In [ ]:
def mergesplit(data_list):
    if len(data_list) <= 1:
        return data_list
    medium = len(data_list) // 2
    left = mergesplit(data_list[:medium])
    right = mergesplit(data_list[medium:])
    return merge(left, right)
In [ ]:
def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0
    
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1
    
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged


In [ ]:
mergesplit(data_list)
In [ ]:
 

알고리즘 분석

  • 알고리즘 분석은 쉽지 않음, 이 부분은 참고로만 알아두자.
    • 다음을 보고 이해해보자
      • 몇 단계 깊이까지 만들어지는지를 depth 라고 하고 i로 놓자. 맨 위 단계는 0으로 놓자.
        • 다음 그림에서 n/$2^2$ 는 2단계 깊이라고 해보자.
        • 각 단계에 있는 하나의 노드 안의 리스트 길이는 n/$2^2$ 가 된다.
        • 각 단계에는 $2^i$ 개의 노드가 있다.
      • 따라서, 각 단계는 항상 $2^i * \frac { n }{ 2^i } = O(n)$
      • 단계는 항상 $log_2 n$ 개 만큼 만들어짐, 시간 복잡도는 결국 O(log n), 2는 역시 상수이므로 삭제
      • 따라서, 단계별 시간 복잡도 O(n) * O(log n) = O(n log n)

프로그래밍 연습
지금 설명한 병합 정렬을 지금 다시 스스로 작성해보세요