[Algorithm]합병정렬(merge sort) 알고리즘 C++

대표적인 nlogn 정렬 알고리즘중 마지막인 합병(병합)정렬 이다.

합병정렬은 항상 nlogn 의 성능을 내는 알고리즘으로 힙정렬과 같고 최악상황의 퀵(n^2) 보다 안정적이다.

하지만 평균적으로 퀵정렬보다 느린 성능을 보이며 알고리즘 구현에있어 힙정렬보다 메모리를 더 많이먹는다.

합병정렬

---

-합병정렬을 쉽게 알수있는 짤(위키백과)-

합병정렬은 분할정복알고리즘이다.  

분할정복은 하나의 문제를 잘개 쪼개어(분할하여) 문제를 해결하는 방법임.

합병정렬이 대표적인 분할정복을 사용하는 알고리즘인데. 정렬할 배열을 하나의 원소로 쪼개어 비교하며 정렬하는 방법이다.

이 정렬은 두가지 순서만 알면 되는데. 

1.분할 (가장 작은 단위까지 분할)

2.정렬 (가장 작은 단위부터 정렬)

과정을 정렬이 완료될때까지 반복이다.

순서대로 알아보겠따.

먼저 정렬할 배열을 만들어준다. 예제로 위짤과같은 배열을 만들어보겠다.

분할

---

1번과정인 분할을 시작한다. 가장 작은 단위까지 분할을 해야한다. 

먼저 배열을 반으로쪼개어 나눈다.

쪼개어진 배얼을 또 쪼갠다.

가작작은단위가 나올때까지 쪼갠다.

여기까지가 분할과정이다.

쪼갤수 없을때까지 나누었다면 이제 정렬을 할 차례다.

합병정렬

---

정렬은 각 구간에서 쪼개어지기 전에 같이있던 원소들끼리 비교하여 정렬한다.

2개짜리를 서로 정렬병합해 4개짜리로 만든다.

마지막으로 정렬이 완료된다.

합병정렬이 완료되었따.

합병이될때 정렬을 하는 로직을 알아보자.

정렬

---

정렬은 각요소의 첫번째원소끼리의 비교로 이루어진다.

비교하여 작은수를 걸러내고 i는 한칸 이동한다.

어느한쪽이 배열범위를 넘어가면 멈추고 남은원소를 뒤에 집어넣는다(정렬이 되어있기때문)

그림설명이 끝났으니 코드로 알아보겠따.

합병정렬.cpp

함수는 크게 두가지다. 

분할,정렬

void partition(int left,int right) 함수에서 분할을 재귀적으로 호출한다. 

void merge(int left, int right) 함수에서 병합하며 정렬한다.

자신이 합병정렬을 만들었다면 nlogn 알고리즘 성공여부를 확인해보자.

2751번: 수 정렬하기 2

 

www.acmicpc.net

합병정렬로 이 문제를 풀경우 메모리 초과가 날수도있다. 이유는 아마 병합하는 함수안에서 임시배열을 선언했기 때문일것이다.