자료의 정렬 - 합병 정렬(Merge sorting)

합병 정렬(Merge sorting)

서로 다른 두 집합을 하나로 합치는 정렬 방식.

전체 원소를 하나의 단위로 분할한 뒤 다시 병합(merge)하면서 정렬된다.

합병정렬(Merge sorting)의 방법

  ① 모든 그룹의 자료를 2개의 그룹으로 분할한다.

  ② 그룹 내의 자료가 1이 될 때까지 계속 분할한다.

  ③ 분할이 끝나면 두 그룹에서 가장 앞에 있는 자료의 크기를 비교해 작은 자료부터 먼저 정렬한다.

  ④ 두 그룹의 자료들이 크기 순으로 정렬될 때까지 반복하여 하나의 그룹으로 만든다.

  ⑤ 다시 남은 그룹에 대해 같은 방법을 수행한다.

  ⑥ 하나의 그룹으로 만들어지면 정렬이 완료된다.

합병정렬(Merge sorting)의 예시

1. 3, 7, 2, 5, 1, 4를 합병정렬을 이용하여 배열해보자.

그룹 내의 자료수가 1이 될 때까지 계속 분할한다.

 

분할된 그룹을 2씩 병합하여 하나의 그룹을 만든다.

 

그룹을 2씩 병합하여 하나의 그룹을 만든다.

 

다시 그룹을 2씩 병합하여 하나의 그룹을 만든다.

 

위 설명은 잘 이해가 되지않는다. 나도 그렇다. 밑의 예시로 천천히 살펴보자.

 

2. 3, 44, 38, 5, 47, 15, 36, 26, 27, 2을 합병정렬을 이용하여 배열해보자.

리스트의 원소를 최소 단위로 전부 분할한다.

 

첫 원소를 지정하고, 그 다음 원소와 크기를 비교한다.

 

좌측의 원소가 더 크므로 넘어간다.

 

첫 번째 원소와 두 번째 원소와 세 번째 원소를 비교하여 정렬한다.

 

네 번째 원소와 다섯 번째 원소를 비교하고, 좌측 원소가 더 작으므로 그냥 넘어간다.

 

첫 번째 원소와 네 번째 원소를 비교한다. 그리고, 두 번째, 세 번째, 다섯 번째 원소를 각각 비교하고,

첫 번째 원소와 네 번째 원소와 같이 정렬한다.

 

여섯 번째 원소와 일곱 번째 원소를 비교한다.

 

여섯 번째, 일곱 번째, 여덟 번째 원소를 각각 비교하고 정렬한다.

 

아홉 번째 원소와 열 번째 원소를 비교하고 정렬한다.

 

다섯 번째부터 열 번째 까지의 원소를 모두 정렬한다.

 

빨간색 그룹과 초록색 그룹이 만들어졌다.

 

이 그룹의 원소들을 각각 비교하며 정렬한다. 정렬완료.

합병정렬(Merge sorting)의 알고리즘

 

.

 

합병정렬(Merge sorting)의 특징

  -비교횟수: nlog₂ n

  -시간복잡도: O(n log n)

 

  -동일한 두 키의 상대 위치가 정렬 과정에서 변하지 않으므로 안정적이다.

  -합병하는 과정에서 입력 배열의 크기만큼의 메모리 공간이 요구된다.

 

 

도움되는 사이트

  - https://visualgo.net/en/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

정렬되는 모습을 실시간으로 보여주는 사이트이다.

사진으로 보는것보다 직접 정렬되는 모습을 보면 이해하기 더욱 쉽다.