이번 포스팅은 합병정렬(Merge sort)에 대해서 정리합니다.
병합정렬이라고도 불리우는 이 정렬은 데이터를 잘게 쪼개고(divide) 크기를 비교해 정렬합니다(conquer) 그리고 이를 합칩니다(merge) 이를 더 이상 합칠 array가 없을 때까지 반복합니다.
위 그림을 보시면 쉽게 나와있습니다. 칸아카데미 페이지에 나와있는 설명인데요. 위에선 2개씩 잘개 쪼갭니다.
쪼갠 뒤 정렬을 하면서 합쳐줍니다. 그러면 최종적으로 정렬된 데이터가 나오게 되겠죠!
그럼 코드로는 어떻게 될까요? 파이썬을 활용해서 코드를 작성해봅니다.
풀 코드를 보기 전에 merge_sort가 어떻게 보이는지 봅니다.
list가 1보다 작거나 같으면 return하고 그게 아니면 mid 값을 // 2로 해서 절반을 기준으로 합니다.
그리고 왼쪽, 오른쪽도 mid 기준으로 보여주고요
아까 그럼에서 보셨다싶이 왼쪽, 오른쪽 나눠지고 정렬을 진행합니다. 위 진행 상황을 보면 leftlist와 rightlist가 나눠지는데 먼저 leftlist 기준으로 또 left와 right로 나눕니다. 이게 1개씩 들어갈 때까지 계속 나눕니다
그리고 맨 처음 rightlist는 밑의 빨간색 화살표 [19,11,2,6,4] 부분에서 다시 활용됩니다. 즉 먼저 left를 기준으로 또 left, right를 나누고 또 나누고.. 이렇게 됩니다.
핵심 함수는 아래와 같습니다. left, right가 주어졌을 때 정렬을 해줍니다.
배열이 둘 다 0 이하이면 멈춥니다. 그때까지 정렬을 계속해줍니다. 만약 완전히 쪼갰을 때 왼쪽, 오른쪽 둘다 1 이상의 데이터가 있다면 left의 0번째 값과 right의 0번째 값을 비교해서 작은 값을 result에 append 시킵니다. 그리고 배열은 1번째 인덱스부터 가져오도록 slice 해야겠죠!
만약 왼쪽만 있다면 왼쪽 값만 append 시킵니다. 오른쪽도 마찬가지입니다.
진행 상황을 보면
정렬되지 않는 리스트가 위와 같이 있다고 가정합니다.
그러면 아까 설명드렸다듯이 왼쪽을 기준으로 데이터를 계속 먼저 자르고 또 거기서 left, right를 만들고 합니다.
여기서는 최종 배열을 보니 leftlist에는 5, rightlist에는 1이 남아있네요. 둘 다 값이 있으니 이 2개를 비교해서 넣습니다.
이제 그 다음은 leftlist[5,1] 다음이니까 rightList 인 [2, 5, 20] 기준으로 들어갑니다.
이렇게 분할 된 것을 다시 merge 하면서 정렬을 해줍니다.
여기서도 또 다시 left, right를 뽑으니까 left에는 5, right는 20이 들어갑니다. 그러면 [5, 20]으로 정렬이 됩니다.
근데 위에서 2 값이 있었는데요. 그럼 2와 5를 비교해서 [2, 5]를 넣습니다. 그러면 left에는 [], right에는 [20]이 남습니다. 아까 로직에서 오른쪽만 있을 경우 right 값을 그냥 빼서 넣었죠. 그래서 [2, 5, 20]이 나옵니다.
이렇게 정렬을 하면서 서로 합쳐주면 됩니다.
최종적으로 위와 같이 정렬이 완료됩니다.
재귀 함수로 되어 있어서 햇갈리긴 하는데
원리는 이렇게 됩니다.
여기까지 합병(병합)정렬에 대해서 알아보았습니다.
'알고리즘&자료구조' 카테고리의 다른 글
| 파이썬 알고리즘 공부 - 숫자 뒤집기(거꾸로 출력), 소수 출력, 배수 출력 (2) | 2019.04.29 |
|---|---|
| 힙 정렬(heap sort)이란? 힙 정렬 공부하기 - 파이썬 자료구조 공부 (2) | 2019.04.24 |
| 파이썬으로 자료구조, 알고리즘 공부하기! 버블 정렬(bubble sort), 쉘 정렬(shell sort) (0) | 2019.04.23 |
| 파이썬으로 알고리즘, 자료구조 공부하기 - 삽입 정렬, 선택 정렬(selection sort, insertion sort) (0) | 2019.04.08 |
| 파이썬으로 알고리즘, 자료구조 공부하기 - 트리(tree), 이진트리(binary tree) (0) | 2019.04.05 |
