20210810 병합정렬(합병정렬)

안녕하세요 틴구입니다.

오늘은 병합정렬에 대해서 설명드리려고 해요~

병합정렬이란 : 합병 정렬(merge sort)은 하나의 배열을 두 개의 균등한 크기로 분할하고 각 분할된 배열을 정렬한 다음, 두 개의 정렬된 부분 배열을 합하여 전체가 정렬된 배열을 얻고자 하는 것이다.

3, 5, 2, 6, 4, 1, 7, 8

의 배열이 구성되어 있다고 하면 

3, 5, 2, 6  |  4, 1, 7, 8

3, 5  |  2, 6  |  4, 1  |  7, 8

3  |  5  |  2  |  6  |  4  |  1  |  7  |  8

이렇게 나뉜다음 돌아가면서 정렬을 이루는 형식입니다

3, 5  |  2, 6  |  1, 4  |  7, 8

2, 3, 5, 6  |  1, 4, 7, 8

1, 2, 3, 4, 5, 6, 7, 8

이런 식으로 요

원리를 알았으니깐 코드구성을 알아봅시다!

우선 template를 이용해 만들 거기 때문에 class를 인라인으로 생성해줍니다

기본 틀은 퀵 정렬이랑 동일한데 추가되는 부분은 병합 정렬은 기본 배열에서 정렬하는 방식이 아닌

새로운 배열을 만든 다음 그 배열에서 정렬을 시키는 방법이기 때문에 T* m_CopyArray를 하나 추가해줍니다.

void push(const T& data) 함수

void push(T* Array, int Count) 함수

 

Sort함수

 

주석으로 코드 분석을 다 해두었으니 설명은 생략하도록 하겠습니다!

처음 위에서 적은 원리만 이해하고 코드를 보면 더 쉽게 이해할 수 있을 겁니다