[알고리즘] 패스트캠퍼스 알고리즘 학습 - 병합 정렬(Merge Sort)

1. 정의

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

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

출처 : https://commons.wikimedia.org/wiki/File:Merge_sort_algorithm_diagram.svg

 

2. 알고리즘 이해

이해를 돕기위한 예시

쪼개는 단계 [1, 9, 3, 2] > [1, 9] , [3, 2] > [1], [9], [3], [2]

더 이상 쪼갤 수 없으면 합병을 진행

작은 데이터를 앞에 큰 데이터를 뒤로 가도록 병합한다.

[1], [9], [3], [2] > [1, 9], [2, 3] > [1, 2, 3, 9]

왼쪽 index 번호와, 오른쪽 index 번호를 활용해서 값을 비교해서 넣어가는 방식으로 진행하면 된다.

 

3. 코드 작성

데이터를 나누는 부분 & 데이터를 합치는 부분

크게 두 개의 함수로 구성될 것을 생각할 수 있다.

 

 

 

 

 

def merge(left, right):
    left_idx, right_idx = 0, 0
    sorted_list = []
    left_len, right_len = len(left), len(right)

    while(left_len > left_idx and right_len > right_idx):
        if left[left_idx] <= right[right_idx]:
            sorted_list.append(left[left_idx])
            left_idx += 1
        else:
            sorted_list.append(right[right_idx])
            right_idx += 1

    while(left_len > left_idx):
        sorted_list.append(left[left_idx])
        left_idx += 1

    while(right_len > right_idx):
        sorted_list.append(right[right_idx])
        right_idx += 1

    return sorted_list

def mergeSplit(data_list):
    if len(data_list) <= 1:
        return data_list

    length = len(data_list)
    mid = length//2
    left = split(data_list[:mid])
    right = split(data_list[mid:])
    return merge(left, right)



## 결과 검증

import random

rand_list = random.sample(range(100), 10)

print(mergeSplit(rand_list))
print(mergeSplit([1, 9, 4, 8, 2, 4, 5, 11]))

>>>
[17, 25, 40, 45, 50, 56, 64, 73, 84, 89]
[1, 2, 4, 4, 5, 8, 9, 11]

 

[알고리즘] 패스트캠퍼스 알고리즘 학습 - 퀵 정렬(Quick Sort)

[알고리즘] 패스트캠퍼스 알고리즘 학습 - 버블정렬

[알고리즘] 패스트캠퍼스 알고리즘 학습 - 삽입 정렬(Insertion Sort)

[알고리즘] 패스트캠퍼스 알고리즘 학습 - 선택 정렬(Selection Sort)