728x90

✨ 합병 정렬 또는 병합 정렬(Merge Sort)는 O(n log n) 비교 기반 정렬 알고리즘이다.
일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하여, 분할 정복 알고리즘의 하나이다.

Merge Sort는 Merge Sort(분할), Merge(병합) 2가지 function으로 나눠서 작성할 수 있다.
Merge를 구현하는 function을 먼저 작성해보겠다.

[ -30, 22] [ 0, 97 ]

left, right 배열에 들어있는 숫자를 오름차순으로 정렬해보자

Merge Function 실행 결과

🎈 Merge function을 실행하면 위와 같은 과정으로 정렬이 진행된다.

각 배열의 가장 첫 번째 값들을 비교하고, 작은 값을 먼저 넣어준다.
이렇게 Merge function은 간단하다. 양쪽 배열을 비교하고 작은 값을 먼저 넣어주면 된다.

아래 Pseudo Code와 이미지를 참고하여 코드를 작성해보자.

 

Merge Function Pseudo Code
Merge Function 이미지화
Merge Function Code

🧨 left, right 2개의 argument를 받고
둘 중 하나의 배열값이 모두 shift()될 때까지 while loop을 반복한다.
가장 첫 번째 index를 비교하고 작은 값을 results 배열에 넣어준다.
둘 중 하나의 배열은 1개의 값이 존재할 것이므로, return 부분에는 result, left, right를 모두 spread해준다.

이렇게 Merge Function을 먼저 작성해줄 수 있다.

다음은 Merge의 전 단계MergeSort Function을 작성해보자(각 배열 분할 기능)

[ 97, 0, 22, -30 ]

위의 배열을 length가 1을 가질 때까지 분할해보자.
이 기능은 끝이 정해져 있는 반복이므로, 재귀를 통해 해결할 수 있다.

Merge Sort 진행 과정

🎈 Merge Sort function을 실행하면 위와 같은 과정으로 정렬이 진행된다.
처음에는 전체 배열의 반으로, 왼쪽에서 또 반으로, 오른쪽에서 또 반으로 반복하여 나눠진다.

아래 이미지를 보며 코드를 어떻게 작성할지 생각해보자.
참고로, Merge Sort는 Merge와 함께 사용할 수 있다.

Merge Sort Function 이미지화
Merge Sort Function Code

🧨 먼저, Base Casearr.length가 1이 되면 그 값을 반환하도록 한다. 우리의 목표는 1개가 남기까지 분할하는 것이기 때문이다.
배열을 반으로 나누는 기능은, Array의 slice helper method를 이용하면 간편하다.
배열의 중앙 기준을 잡기 위해 center를 구해주고,
그 기준으로 slice(0, center), slice(center)를 진행해주면 leftright를 구할 수 있다.
( Math.floor(), slice() 사용법은 JavaScript - helper Method 카테고리에서 확인 가능)

그리고 마지막으로, 이 나눠진 element를 merge function을 이용해서 병합해주면 된다.

Merge Sort and Merge Function

Merge Sort와 Merge Function이 진행되는 전체 이미지

+ Recent posts