병합 병렬(merge sort)

1) 병합 병렬(merge sort) 이란?

재귀 용법을 활용한 정렬 알고리즘

- 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

- 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

- 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

 

Merge sort - Wikipedia

 

2) 알고리즘 구현

 

▼ 파이썬

- 어떤 데이터 리스트가 있을 때, 리스트를 앞뒤로 자르는 코드 작성해보기 (일반화)

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

 

- 재귀 용법 활용하기

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

* mergesplit 함수 만들기

- 만약 리스트 갯수가 한 개이면 해당값 리턴

- 그렇지 않으면, 리스트를 앞뒤 두 개로 나누기

- left = mergesplit(앞)

- right = mergesplit(뒤)

- merge(left, right)

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

 

- merge 함수 만들기

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

* merge 함수 만들기

- 리스트 변수 하나 만들기 (merged)

- left_point, right_point = 0

- while len(left) > left_point and len(right) > right_point:

  = 만약, left_point 나 right_point 가 이미 left 또는 right 리스트를 다 순회했다면, 그 반대쪽 데이터를 그대로 넣고, 해당 인덱스 1 증가

  = ~~~

def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0
    
    # case1 - left/right 둘 다 있을 때
    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
    
    # case2 - left 데이터가 없을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
   
    # case3 - right 데이터가 없을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
        
    return merged

1. merged 리스트 변수 선언하기

2. left_point, right_point 를 0 으로 초기화하기

3. while len(left) > left_point and len(right) > right_point 일 때

   - 만약 left[left_point] > right[right_point] 이면, merged 에 right[right_point] 를 추가하고, right_point 값을 1 증가

   - 만약 left[left_point] <= right[right_point] 이면, merged 에 left[left_point] 를 추가하고, left_point 값을 1 증가

4. left 혹은 right 의 리스트가 빈 상황이 생기면 case2 혹은 case3 의 while문으로

   - len(left) > left_point 일 때, merged 에 left[left_point] 를 추가하고 left_point 값을 1 증가

   - len(right) > right_point 일 때, merged 에 right[right_point] 를 추가하고 right_point 값을 1 증가

 

 

* 최종 코드

def mergesplit(data):
	if len(data) <= 1:
    	return data
    
    medium = int(len(data) / 2)         // 입력된 데이터 개수를 int 화하여 중간값 도출
    left = mergesplit(data[:medium])    // data(리스트) 중간값을 기준으로 왼쪽
    right = mergesplit(data[medium:])   // data(리스트) 중간값을 기준으로 오른쪽
    return merge(left, right)           // merge 함수 호출

def merge(left, right):
    merged = list()		        // merged(리스트)
    left_point, right_point = 0, 0
    
    # case1 - left/right 둘 다 있을 때
    while len(left) > left[left_point] and len(right) > right[right_point]:
        if left[left_point] > right[right_point]:   // left 의 데이터값이 큰 상황
            merged.append(right[right_point])       // 오름차순이므로 right 의 데이터 삽입
            right_point += 1    // right_point = 0 인 데이터값이 입력됐으므로 + 1
        else:
            merged.append(left[left_point])         // 위와 동 
            left_point += 1
    
    # case2 - left 만 남았을 때
    while len(left) > left[left_point]:     // right_point 가 최고점에 달한 상황
        merged.append(left[left_point])     // left 의 데이터 삽입
        left_point += 1
    
    # case3 - right 만 남았을 때
    while len(right) > right[right_point]:  // left_point 가 최고점에 달한 상황
        merged.append(right[right_point])   // right 의 데이터 삽입
        right_point += 1
    
    return merged

 

결과

import random

data = random.sample(range(100), 10)
print(mergesplit(data))

 

 

3) 알고리즘 분석

시간복잡도는 평균 O(n*logn), 최선 O(n*logn), 최악 O(n*logn) 으로 동일하다.

pivot 값이 없고, 항상 반으로 나뉜다는 특징이 있다. 바로 이 특징이 단계의 크기가 logN 이 되도록 만들어 준다.

 

 

 

참고)

1. 합병 정렬 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

합병 정렬 - 위키백과, 우리 모두의 백과사전

2. 패스트캠퍼스 '코딩 알고리즘 온라인 완주반'

3. 7. 병합 정렬(Merge Sort) : 네이버 블로그 (naver.com)

7. 병합 정렬(Merge Sort)