[삼성 알고리즘] 정렬 알고리즘(버블, 선택, 삽입, 병합, 퀵) 2

지난 포스팅에이어 병합 정렬 알고리즘을 진행하겠습니다.

이전에 포스팅을 진행한 버블,선택,삽입 정렬에 대한 내용은

 

https://bluemoon-1st.tistory.com/13?category=851281

 

으로 가시면 됩니다~~!

 

1. Merge Sort

병합 정렬은 Divide & Conquer 알고리즘의 대표적인 알고리즘 중 하나입니다.

먼저 동작 방식은 N개의 데이터를 이분법을 통해 N/2개로 쪼개고 쪼개진 2개의 N/2를 각각 이분법을 통해 N/4의 4가지로 쪼갭니다.

이 처럼 N/2, N/4, N/8 ...식으로 쪼개는 작업을 진행하고 합칠 때 데이터의 크기를 비교해서 정렬된 형태로 합치는 과정을 진행함으로써 N개의 데이터 정렬을 진행합니다.

 

위와 같이 8개의 데이터가 있는 경우 이분법을 통해 4개, 2개, 1개 씩으로 데이터를 쪼개는 작업이 가장 먼저 진행됩니다. 쪼개는 작업은 logN번 만큼 진행됩니다.

 

 

그 후 비교과정을 거쳐 Conquer 작업을 진행합니다. 비교과정은 먼저 가장 좌측의 데이터(정렬이 이미 되어있으므로)를 비교하고 그 후에 데이터가 한쪽으로 치우쳐진 즉 우측과 같이 1,4 와 6,7이 있는 경우에는 1과 6 그리고 4와 6 비교과정 즉 2 번의 비교과정을 통해서 바로 Conquer를 진행할 수 있습니다.

비교과정은 좌측과 같이 가장 좌측 비교 후 작은 값을 넣고 그 다음 값을 비교하는 방법을 이용합니다.

간단히 정리하면 좌측의 3,5 우측의 2,9에 대하여

3과 2를 비교 하고 2를 가장 좌측에 넣게되면 좌측의 3,5 우측의 9만 남게되고 여기서

3과 9를 다시 비교하는 방법으로 진행됩니다.

 

하지만 최악의 경우 번갈아 가며 비교하는데 이 경우 N번의 비교가 진행될 수 있습니다. 즉 결과적으로 logN의 분할과정과 N번의 Conquer과정의 곱셈이 만큼의 연산이 진행되므로 O(NlogN)의 성능을 가지게 됩니다.

 

Merge Sort의 경우 최악, 평균, 최상 모두 NlogN을 가지는 특징이 있습니다.

 

추가적으로 Merge Sort에 대해 정리하면...

기존 정렬을 진행해야되는 배열을 제외하고 외부 배열을 추가로 이용하므로 메모리 공간이 많이 필요하는 단점이 존재하는 아쉬운 측면이 존재합니다.

 

다음 포스팅은 Quick Sort로 진행하겠습니다.

 

감사합니다!