[합병정렬] 자바스크립트 MergeSort

오늘은 3 대장 (삽입, 선택, 버블) 이후 좀 더 복잡하지만 빠른 합병 정렬에 대해서 정리해 보겠습니다.

 

합병 정렬 (MergeSort) 

합병 정렬 원리는 배열을 각각 하나의 원소까지 나누어 줍니다. 

즉 [3,2,1] 이라는 배열이 있으면 => [3] [2] [1] 

이렇게 나눠진 배열을 다시 정렬하면서 하나에 배열로 합치는 과정입니다. [1,2,3] 

 

Example

[6,3,1,5,2] 라는 배열이 있다고 가정하고 예시를 들어 보겠습니다.

중앙값을 기준으로 왼쪽과 오른쪽을 나눠줍니다.

배열 원소가 한개가 남을 때까지 나눠줘야 합니다.

 

// 왼쪽

[6,3,1,5,2] => [6,3] [1,5,2]

[6,3] => [6] [3]

 

// 오른쪽

[1,5,2] => [1] [5,2]

[5,2] => [5][2] 

 

각각 한개로 나눠진 원소들을 비교 정렬해나가면서 하나의 배열로 합칩니다.

[6] [3] => [3,6]

[5] [2] => [2,5]

[1] [2,5] => [1,2,5]

[3,6] [1,2,5] => [1,2,3,5,6]

 

즉 중요한 개념은 아래 사항 입니다.

1. 중앙값을 찾고 배열을 왼쪽과 오른쪽으로 나눈다.

2. 재귀 함수를 통해서 배열 원소가 1개가 남을 때까지 나눈다.

3. 1개까지 남은 오른쪽 값과 왼쪽 값을 정렬하면서 합친다.

4. 최종적으로 정렬된 배열을 리턴해준다.

 

 

자바스크립트 코드

function mergeSort(arr) {
  if (arr.length === 1) return arr;
  let mid = Math.floor(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

// [6,3,1,2,5]

function merge(arr1, arr2) {
  let arr = [];
  let i = 0;
  let j = 0;
  // 왼쪽 배열과 오른쪽 배열을 비교하면서
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      arr.push(arr1[i]);
      i++;
    } else if (arr1[i] >= arr2[j]) {
      arr.push(arr2[j]);
      j++;
    }
  }
  while (i < arr1.length) {
    arr.push(arr1[i]);
    i++;
  }
  while (j < arr2.length) {
    arr.push(arr2[j]);
    j++;
  }

  return arr;
}

const result = mergeSort([6, 3, 1, 5, 2]);
console.log(result);

 

 

merge() 

각각 배열을 인자로 받고 각 배열을 비교 정렬하면서 arr이라는 내부 배열에 정리해서 return 해 주는 함수입니다.

merge([1, 2, 5], [3, 4, 6]) 이렇게 실행했을 때 결괏값으로 [1,2,3,4,5,6]이 반환됩니다.

주의할 점으로는 각 배열에 정렬된 값들이 들어와야 하는 것입니다.

그렇지 않으면 정렬이 제대로 되지 않습니다.

각각 배열에 인덱스 값을 i , j = 0으로 설정해 줍니다.

첫 번째 while

(i < arr1.length && j < arr2.length) : arr1 , arr2 두 개 배열중 어느 하나가 정렬이 완료되면 종료됩니다.

if (arr1 [i] < arr2 [j]) : 오른쪽 값이 더 크다면 왼쪽 값을 먼저 arr = [] 배열에 넣어줍니다.

그 후 그다음 배열 인덱스 값을 비교하기 위해서 i++을 해줍니다.

else if(arr1 [i] >= arr2 [j]) : 왼쪽 값이 더 크거나 같으면 arr2 [j] 값을 arr = [] 배열에 넣어줍니다.

첫 번째 조건과 다르게 같거나 크면 이라고 해준 이유는 두 값이 동일하면 배열 안에 들어가지지 않기 때문에 값이 동일한 경우에도 

정렬될 수 있도록 같거나 크면이라는 설정을 해준 것입니다. 물론 첫 번째 비교 때 하셔도 상관없습니다.

두 번째 , 세 번째 while : arr1, arr2 중 어느 하나 배열이 완료되면 나머지 배열 값들을 arr = [] 배열에 넣어줍니다. 

애초에 여기 들어오는 배열들은 정렬이 되어 있기 때문에 그냥 바로 넣어도 됩니다.

정렬된 배열 값을 return 해 줍니다.

 

mergeSort() 

정렬되지 않은 배열을 인자 값으로 받습니다.

if (arr.length ===1) return arr : 이 부분은 나중에 재귀 함수로 mergeSort()를 나누면서 계속 호출할 건데 그때 만약 

인자 값이 하나면 그 인자를 리턴하는 부분에서 쓰입니다.

let mid = Math.floor(arr.length / 2) : 배열의 왼쪽 값과 오른쪽 값을 나눌때 소수점 값이 생기지 않기 위해서 사용됩니다.

let left = mergeSort(arr.slice(0, mid))  , let right = mergeSort(arr.slice(mid)) 

-> 각각 중앙값을 기준으로 왼쪽값 오른쪽 값으로 나누는데 값이 1개가 남을 때까지 재귀 호출해줍니다.

위에 Example에 썼던 예시처럼 나누어집니다.

return merge(left, right) : 각각 원소가 한 개까지 남았을 때 하나도 합쳐지면서 그 값을 정렬된 배열을 리턴해 줍니다.

 

결과 

잘 정렬되어 있는 걸 확인할 수 있습니다.

 

시간복잡도 : O(nlogn) 으로 다른 정렬에 비해 좋은편 입니다.