알고리즘 - 병합정렬

병합정렬

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

알고리즘을 이해해보자.

• 데이터가 네 개 일때.
  • ex) data_list = [1, 9, 3, 2]
    • 먼저 [1, 9], [3, 2]로 나누고
    • 다시 앞 부분을 [1], [9]로 나눈다.
    • 정렬해서 합친다. [1, 9]
    • 뒷 부분도 [3], [2]로 나눈다.
    • 정렬해서 합친다. [2, 3]
    • 이제 [1, 9]와 [2, 3]을 합친다.
      • 먼저, 1과 2를 비교하여 더 작은 수인 1을 리스트에 append
        -> [1]
      • 9 > 2 이니 [1, 2]
      • 9 > 3 이니 [1, 2, 3]
      • 9 밖에 안 남았으니 [1, 2, 3, 9]

작은 부분부터 작성해서 하나씩 구현하기

def split_func(data):
    medium = int(len(data) / 2)
    print (medium)
    left = data[:medium]
    right = data[medium:]
    print (left, right)
    
split_func([1, 5, 3, 2, 4])

실행결과

2
[1, 5] [3, 2, 4]

재귀용법 활용하기

다음 문장을 코드로 작성해보자.(merge함수는 있다고만 가정)

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

def mergesplit(data):
	if len(data) <= 1:
    	return data
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    
    return merge(left, right)

merge 함수 만들기

• 여기서 목표는 left와 right의 리스트 데이터를 정렬하여 새로운 list로 return 하는 것이다.
• left와 right는 이미 정렬된 상태이거나 데이터가 하나 뿐이다.

def merge(left, right):
	merged = list()
    left_index, right_index = 0, 0
    
    #case1 left, right 둘 다 있을 때
    while left_index < len(left) and right_index < len(right):
    	if left[left_index] < right[right_index]:
        	merged.append(left[left_index])
            left_index += 1
        else:
        	merged.append(right[right_index])
            right_index += 1
     
    #case2 left 데이터가 없을 때
    while left_index < len(left):
    	merged.append(left[left_index])
        left_index += 1
        
    #case3 right 데이터가 없을 때
    while left_index < len(left):
    	merged.append(right[right_index])
        right_index += 1
        
    return merged
    
def mergesplit(data):
	if len(data) <= 1:
    	return data
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    
    return merge(left, right)

실행결과

[8, 12, 24, 40, 47, 70, 81, 87, 92, 96]