[알고리즘] 병합정렬 알고리즘 | Merge Sort | C++코드 해석
분할정복(Divide and Conquer) 알고리즘을 공부하고있습니다.
병합정렬을 이해해보겠습니다, 우선은 코드는 이렇게 생겼습니다
코드를 이해하기 쉽도록 병합정렬의 개념과 예시그림을 설명하겠습니다!
병합정렬은 분할과 정렬로 나눌수있습니다.
먼저 처음과 끝의 중간에서 두 개로 분할합니다.
이후 분할된 블록들을 계속해서 최소단위까지 분할해줍니다.
8개의 수열을 분할하는 과정을 예로 들면,
이런 식이 됩니다.
코드를 보면 이에 재귀함수를 이용하였는데요, 빨간색 숫자는 재귀함수에 따라 분할이 되는 순서입니다.
재귀함수가 머리아프신분들은 저 순서를 보시면 직관적으로 바로 이해가 되실 거에요!
분할이 끝났으면 5번에서 정렬&병합 한번, 8번에서 한번,
8번 병합이끝나고 6번에 돌아와서 한번, 6번에서 끝나고 2번에서 한번... 이런식으로 이루어집니다.
5번 분할이 끝난후 정렬&병합되는 과정은
이렇습니다. i는 왼쪽 수열, j는 오른쪽 수열의 포인터를 담당한다고 생각하면됩니다.
한칸짜리로는 각각 i와 j가 어떤 역할을 하는지 바로 알기 어려움으로
8번 병합이 끝난후 6번에서 이루어지는 정렬&병합을 살펴보겠습니다
코드에 써있듯이, 왼쪽블럭과 오른쪽블럭을 비교하며 작은쪽이 임시배열인 B에 차례차례 들어가게됩니다.
B에 채워넣은다음에는 채워넣어진 쪽의 포인터가 한칸 전진하게됩니다.
이러한 전체적인 과정을 움짤로 보자면,
이런식이 됩니다 ;)