알고리즘 문제풀이 7

mergesort(합병정렬) 구현에 대한 알고리즘이다.

mergesort란?

합병정렬에 대한 설명(참고 블로그)
즉 주어진 배열을 각각의 개별 요소로 이루어진 배열이 될 때까지, 둘로 쪼개는 과정을 진행한다.
그리고 다 쪼개진 요소들을 크기 비교하여 합쳐준다.
즉 합병할 때, 실제 정렬이 이루어진다고 해서 합병정렬이라 부른다.
(개인적으로 해당 정렬의 효율적인 측면에서 조금 이해가 가지 않는다.)

->하나의 배열이 쪼개지고 다시 합쳐지는 과정이 재귀적으로 이루어진다.
(두 부분 리스트로 나누어지기 전까지)
->두 부분 리스트가 되었을때, 두개의 배열을 순회하면서 각 인덱스의 요소들을 크기 비교하여
더 작은 수를 먼저 새로운 배열에 넣어준다.
(가령, 1부분 리스트의 첫번째 요소 VS 2부분 리스트의 첫번째 요소에서 1부분 리스트의 요소가
더 작으면 해당 요소를 가상의 리스트에 넣어주고,
1부분 리스트의 두번째요소 VS 2부분 리스트의 첫번째 요소를 비교해서 더 작은 요소를 넣어주는 방식)

//우선 주어진 배열을 중간 인덱스 값을 기준으로 쪼개준다.
var mergeSort = function(array) {
 // 재귀함수 탈출조건 단일 요소로 구성된 배열이라면, 리턴
   if (array.length === 1) {
      return array;
    }
    let middle = Math.floor(array.length / 2); // 배열의 중간 값
    let left = array.slice(0, middle); // left side items
    let right = array.slice(middle); // right side items
    return merge(mergeSort(left), mergeSort(right));
  //이 부분에서 궁금 한것이, 각 쪼개진 요소들이 완전히 쪼개지고 합병 작업이 들어갈까? 아니면
  //동시다발적으로 이루어 질까? 즉 쪼개진 요소들의 크기비교 합병과, 각 부분 배열들의 쪼개짐이 말이다.
  //정답은 쪼개지는 작업우선으로 이루어진다. (디버깅 진행해보니 알게 됨)
  //위의 참고 블로그의 그림처럼 실제로 요소가 각 하나로 쪼개진 후에 merge 작업이 시작된다.
  //각 배열들이 쪼개지고 왼쪽 배열과 오른쪽 배열은 크기 비교후 합병 작업으로 들어간다.
  //그와 동시에 각 부분 배열들이 요소가 한개가 될때까지 쪼개지는 작업과 합병 작업이 동시에 이루어진다.
  //이때, mergesort에 들어가는 배열의 길이가 1개일 경우, return merge(array)가 아니라, 
  //그냥 return array 인 이유는, 요소가 진짜 단 하나일 경우, 크기 비교할 이유가 없기 때문이다.
}

//왼쪽과 오른쪽 값을 비교하는 함수
function merge(left, right) {
  let result = []; //크기 비교후 각 요소를 담을 결과 배열
  let leftIndex = 0;
  let rightIndex = 0;

  // left items와 right items 비교
  while(leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
  return result.concat(left.slice(leftIndex), right.slice(rightIndex))
}

디버깅을 통한 위의 코드의 구현 순서

가상의 배열 [27,34,8,2,15,10]
1. mergesort 함수를 통해서 해당 함수가 계속 쪼개진다.
그리고 요소가 각 한개로 쪼개진 [34],[8]에 대해 먼저 크기 비교를 시작한다.
2. merge 함수를 통해서 크기 비교후, result = [8,34]가 된다.
3. 그리고 mergesort 에서 [27]과 그 오른쪽 부분 배열이 비교되는데, 이 때,
merge 함수를 통해 크기 비교후 재정렬되어서 리턴된 함수가 [27]과 비교될 오른쪽 배열로서
리턴되어 값이 바뀌어서, [27]과 정렬된 [8,34]가 비교된다.

즉, 합병 및 크기비교 함수를 통해서, 재정렬된 함수가 반영되어서 다른 부분 배열들과 비교되고
그렇게 합병되어 가는 부분이 핵심인듯 하다.

mergeSort의 효율성

• 생긴 것과는 다르게(즉 복잡하지만) 효율적인 정렬이다.
  -> 연결리스트와 사용된다면 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
  따라서 효율적이다.
  why? (해당 부분이 잘 이해가 가지 않는다)
  연결리스트를 사용하지 않는 경우, 두 집합을 서로 비교하여 정렬된 상태로 합친걸 잠시 옮겨둘 배열 또는 리스트가 필요하다.
  하지만 레코드를 '연결 리스트'로 구성하여 구현할 경우
  쪼개고, 합치고, 정렬할 때 포인터 값만 수정해주면 되므로 새로운 배열을 만들어서 재선언해줄 필요가 없다.

mergeSort의 시간복잡도

• 분할단계는 단순히 분할을 하므로 별도의 연산이 수행되지 않아서, 시간 복잡도를 계산할 필요가 없다.
• 합병 비교 단계
  1) 합병단계는 일종의 트리구조로 비유해서 생각하면 그 단계의 깊이만큼의 시간복잡도를 가진다.
  합병정렬은 주어진 배열을 둘 씩 쪼개고 다시 합치는 과정이기 때문에, 각 쪼개진 배열이
  다시 합쳐지는 단계의 수는 log₂n 이다.
  즉, n이 배열의 갯수라고 가정했을 때, 2^단계의수 = 배열의 갯수 가 되는 것.
  2) 비교 정렬의 단계는 최악의 경우를 고려했을 때 당연히, n이다.

따라서 시간 복잡도는 nlog₂n이다.