본문 바로가기
Algorithm/Sorting

[Python] Merge Sort: 병합 정렬

by JKyun 2018. 3. 30.

안녕하세요. 우주신 입니다.


오늘은 병합 정렬(Merge Sort)에 대해 포스팅하겠습니다.


병합 정렬은 정렬되지 않은 전체 데이터를 하나의 단위로 분할한 후에 

분할한 데이터들을 다시 병합하며 정렬하는 방식 입니다.


즉, Divide: n개의 데이터를 n/2개 데이터로 나누고 2개의 리스트에 넣습니다.

Conquer: 2개의 리스트들의 데이터가 하나가 될 때까지 재귀적으로 나눕니다.

Combine: 각각의 2개의 리스트를 병합 합니다.


시간 복잡도는 최악의 경우 O(nlogn)로 이전 포스팅에서 소개했던 insertion sort보다 효율적인 알고리즘 입니다.



코드를 통해 자세히 보겠습니다.


우선, 데이터를 리스트로 입력 받겠습니다.

입력 받은 데이터를 띄어쓰기 기준으로 구분하여 이를 정수형으로 리스트에 저장하는 코드 입니다.



위의 코드가 헷갈리시는 분들은 똑같은 기능을 하는 밑의 코드를 참고해주세요. 



병합 정렬 알고리즘은 merge_sort 함수와 merge 함수를 이용합니다.


1. merge_sort


8 7 6 5 4 3 2 1


8 7 6 5        4 3 2 1


8 7        6 5            4 3        2 1


8     7      6    5          4    3      2    1


2. merge


8     7      6    5          4    3      2    1


7 8        5 6            3 4         1 2


5 6 7 8           1 2 3 4


1 2 3 4 5 6 7 8



merge_sort 함수는 정렬되지 않은 리스트를 인자로 받습니다.



if 구문을 통해 정렬되지 않은 리스트의 데이터가 하나 이하이면 그대로 반환 해줍니다.

그렇지 않은 경우에는 우선, 정중앙을 기준으로 리스트를 나눠야 하는데, 이 때 정중앙의 위치를 mid라는 변수에 저장합니다.

mid를 기준으로 left와 right를 나누고, 다시 각각의 left와 right를 merge_sort의 인자로 전달해 줍니다. (재귀)


하나의 요소로 다 나눴으면 merge 함수에 left1, right1 인자를 넣어 병합 과정으로 넘어갑니다.



정렬된 데이터들을 넣을 sorted_list를 만들어주고,

left, right 길이 안에서 각각 0번째 자리부터 비교를 하고 작은 값을 sorted_list에 넣습니다.

left, right를 비교가 다 끝난 후, 남아 있는 값들을 다 넣어줍니다.



출력 결과를 확인해보면,



깔끔하게 정렬된 것을 확인할 수 있습니다.




'Algorithm > Sorting' 카테고리의 다른 글

[C] Countsort:: 계수정렬  (2) 2018.07.28
[C] Quicksort:: 퀵정렬  (2) 2018.06.24
[C] Heap Sort:: 힙정렬  (0) 2018.06.23
[Python] Insertion Sort: 삽입정렬  (1) 2018.03.29

댓글