[알고리즘] 합병정렬 알고리즘(분할과 정복 알고리즘 유형 중 하나) With JS

합병정렬 알고리즘

분할 정복(Divide and Conquer) 알고리즘 중 하나로, 배열을 반으로 나누어 각각을 재귀적으로 정렬하고, 그 결과를 합쳐서 정렬된 배열을 생성하는 알고리즘입니다.
 
 
* 분할과 정복 알고리즘의 원리
접은 글 내에 글자 중복이 있습니다. 중복된 부뷰이 지우고  수정한 부분이었는데, 수정 시에는 안 보이는데 등록 후에는 보이는 이상한 버그가 있네요

 분할 정복 알고리즘의 일반적인 구조는 다음과 같습니다.

• 분할(Divide) : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
• 정복(Conquer) : 각각의 작은 문제를 동일한 방법으로 순환적으로 해결
• 합병(Combine) : 작은 문제의 해를 합하여 원래 문제에 대한 해를 구함

 

합병정렬도 위 구조에 따라, 배열을 분할하고, 정렬 후 합병하는 방식으로 동작하며, 이를 반복하여 최종적으로 정렬된 배열을 얻습니다.

 -----------------------------------

* 작은 문제의 해

 

작은 문제의 해란, 주어진 문제를 해결하기 위해 부분적으로 풀어낸 문제의 해답을 의미합니다. 예를 들어, 큰 배열을 정렬해야 한다면 작은 문제로는 배열의 일부분만 정렬하면 됩니다. 이렇게 작은 문제의 해를 구하고 이들을 합쳐서 최종적인 문제의 해를 구하는 것이 분할정복 알고리즘의 핵심 아이디어 중 하나입니다. 이렇게 분할하여 해결한 작은 문제의 해를 이용하여 전체 문제의 해를 구하는 것이 분할정복 알고리즘의 핵심 아이디어 중 하나입니다.

---

합병정렬 알고리즘의 실행 과정

1. 입력 배열을 반으로 나누어 두 개의 배열로 분할합니다. 2. 분할된 각각의 배열을 재귀적으로 합병 정렬 알고리즘을 호출하여 정렬합니다. 3. 분할된 배열을 합병하여 정렬된 결과를 반환합니다.

---

코드

각 유형은 사용된 세부 메서드나 배열에 대한 접근 방식에 약간 차이가 있을 뿐 거의 동일한 방식에 따른 동일한 원리에 의해 동일한 결과를 출력합니다. 다만  사용하는 메서드에 따라서 배열의 길이 등에 따라 성능 측면에서 차이가 발생할 수 있습니다.
 
즉, 같은 알고리즘의 구현 방식이라도 세부 구현 내용에 따라서는 그 성능 차이가 제 각각 이므로 상황에 따라서 효율적으로 재사용할 필요가 있습니다.
 
유형1)

function mergeSort(arr) {
  // 재귀적으로 호출하여 배열을 반으로 쪼갠다.
  if (arr.length <= 1) {
    return arr;
  }
  
  //배열을 구분하기 위한 중간 인덱스를 구한다.
  const mid = Math.floor(arr.length / 2);
  
  // mid(중간위치의 인덱스)을 기준으로 왼쪽/오른쪽 배열을 구분한다.
  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);

  // 재귀 호출을 통해 각각 정렬한다.
  const sortedLeftArr = mergeSort(leftArr);
  const sortedRightArr = mergeSort(rightArr);

  // 정렬된 배열을 하나로 합치기 위해 merge 함수를 호출한다.
  return merge(sortedLeftArr, sortedRightArr);
}

// left, right로 각각 정렬된 배열을 합치는 연산을 수행하는 함수(merge)
function merge(leftArr, rightArr) {

   //정렬된 배열이 저장되는 변수이다.
  let sortedArr = [];

  // 왼쪽 배열과 오른쪽 배열의 첫번째 인덱스를 비교하여 작은 값을 새로운 배열에 push한다.
  // 이 과정은 두 배열 중 하나의 배열 길이가 0이 될 때 까지 반복한다.
  while (leftArr.length && rightArr.length) {
    if (leftArr[0] < rightArr[0]) {
      sortedArr.push(leftArr.shift()); 
    } else {
      sortedArr.push(rightArr.shift());
    }
  }

  // 남은 요소들을 새로운 배열에 push한다.
  while (leftArr.length) {
    sortedArr.push(leftArr.shift());
  }
  while (rightArr.length) {
    sortedArr.push(rightArr.shift());
  }

  return sortedArr;
}

 
유형2)

function mergeSort(arr) {
  // 배열의 길이가 1 이하면 정렬이 불필요하므로 그대로 반환한다.
  if (arr.length <= 1) {
    return arr;
  }

  // 배열의 중간 인덱스 값을 구한다.
  const middle = Math.floor(arr.length / 2);

  // 중간 인덱스를 기준으로 왼쪽, 오른쪽 배열을 나눈다.
  const leftArr = arr.slice(0, middle);
  const rightArr = arr.slice(middle);

  // 재귀 호출을 통해 각각 정렬한다.
  const sortedLeftArr = mergeSort(leftArr);
  const sortedRightArr = mergeSort(rightArr); 

  // 정렬된 두 배열을 합병한다.
  return merge(sortedLeftArr, sortedRightArr);
}

function merge(leftArr, rightArr) {
  let resultArr = [];
  let leftIdx = 0;
  let rightIdx = 0;

  // 두 배열을 비교하여 작은 값을 결과 배열에 추가한다.
  while (leftIdx < leftArr.length && rightIdx < rightArr.length) {
    if (leftArr[leftIdx] < rightArr[rightIdx]) {
      resultArr.push(leftArr[leftIdx]);
      leftIdx++;
    } else {
      resultArr.push(rightArr[rightIdx]);
      rightIdx++;
    }
  }

  // 아직 남아있는 요소를 결과 배열에 추가한다.
  return resultArr.concat(leftArr.slice(leftIdx), rightArr.slice(rightIdx));
}

 
유형3)

function merge(arr1,arr2){
   let results =[]
   let i=0;
   let j=0;
  //두 배열의 길이 모두 보다 i,j 크기가 작을 때 까지 반복
   //허나 두 배열의 길이가 서로 달라 모두 돌기 전에 반복이끝난다.
   while(i<arr1.length &&j < arr2.length) {
       if(arr1[i]<arr2[j]){
           results.push(arr1[i]) //비교 했을 때 더 작은 값을 빈배열에 넣고 ++ 한다.
           i++;
} else{
           results.push(arr2[j])
           j++
}
}
   //나머지 배열요소에 대한 반복을 돌려서 위에서 마무리 못한 나머지를  배열에 합친다.
   while(i<arr1.length){
       results.push(arr1[i])
       i++
       
}
   while(j<arr2.length){
       results.push(arr2[j])
       j++
}
   
   return results
}

function mergeSort(arr){
   //배열의 길이가 1이 될 때 까지 다음 반복으로 넘어간다.
   if(arr.length <=1) return arr
   
//배열을 자르기 위한 중간값을 구하기 위한 표현식
   let mid = Math.floor(arr.length/2);
 
  //정렬된 배열을  왼쪽과 오른쪽으로 구분한 배열로 만든다. 
   // 왼쪽 배열은 0부터 중간까지, 오른쪽 배열은 중간부터 끝까지
   // 반복하면서 리턴되는 값을 변수에 담는다. 
   // 재귀를 통해 주어진 배열의 길이가 1이 될 때 까지 반복한다. (계속 분해)
   let left = mergeSort(arr.slice(0,mid)); //mid 인덱스 –1 요소 까지 포함한다.
   let right = mergeSort(arr.slice(mid)); //mid 인덱스 요소를 포함해서 나머지 요소 모두 포함
  
   // 각각 저장된 배열들을 하나로 합치고 정렬하기 위해 1단계 합병함수를 호출한다.
   return merge(left, right)
}
mergeSort([10,24,76,73,72,1,9])

// mergeSort 를 실행하는 경우 재귀호출이 될 수록 배열의 길이가 0으로 줄어드는 것을 확인할 수 있다
/**[10,24,76,73,72,1,9]
/  [10,24,76] left
/  [10] left
/  left =[10]
/  [24, 76] left 
/  min = 1
/  [24] 
/  left =[]
*/

---

시간복잡도와 공간복잡도

 
합병정렬의 시간복잡도와 공간복잡도는 입력 데이터의 크기와 형태에 따라 다양하게 나타납니다.
 

• 최적의 경우

입력 데이터가 이미 정렬되어 있을 때, 합병정렬의 시간복잡도는 O(nlogn)입니다.
이는 입력 데이터를 반으로 나누어 가며,각각의 분할된 데이터들을 한 번씩만 비교하면 되기 때문입니다.
 
공간복잡도는 O(n)입니다.

• 최악의 경우

입력 데이터가 역순으로 정렬되어 있을 때, 합병정렬의 시간복잡도는 여전히 O(nlogn)입니다.
하지만, 분할과 합병의 과정에서 매번 모든 데이터를 비교하므로 계수에 상수가 크게 붙어서 실제 실행 시간이 더 오래 걸릴 수 있습니다. 
 
공간복잡도는 여전히 O(n)입니다.
 

• 보통의 경우:

입력 데이터가 무작위로 주어졌을 때, 합병정렬의 시간복잡도는 여전히 O(nlogn)입니다. 
분할과 합병의 과정에서 매번 절반으로 나누어 가며 비교하는 것이 최선의 방법이기 때문입니다. 
 
공간복잡도는 O(n)입니다.
 

---

따라서 합병정렬은 대부분의 경우에 대해 일정한 시간복잡도를 가지며, 
공간복잡도 또한 상대적으로 적은 메모리를 사용하기 때문에 널리 사용되는 정렬 알고리즘 중 하나입니다.
 

 

---

공간복잡도가  최적, 보통, 최악 모두 O(n) 인 이유

 

공간 복잡도는 보조 배열을 사용하기 때문에, 
합병정렬의 경우 최악의 경우에도 입력 배열의 크기만큼의 공간을 사용하게 됩니다. 
따라서 공간 복잡도는 O(n)입니다.
 
예를 들어, 정렬된 분할 배열을 합치기 위해
두 배열의 값을 비교하여 작은 값을 보조 배열에 넣게 됩니다.
이때, 합병 과정에서 사용되는 배열을 보조 배열 이라 합니다.
 
(즉, left, right 를 기준으로 나눈 요소를 담는 배열을 말하는 것입니다.).
 
따라서, 합병정렬의 경우 최악의 경우에도 
입력 배열의 크기만큼의 공간을 사용하게 되므로,
공간 복잡도는 O(n)이 됩니다.