[알고리즘 | JS] sorting algorithm(정렬 알고리즘)4 - merge sort

이전에 배웠던 3가지 기초 sorting 알고리즘은 소규모의 데이터(e.g.)20개의 요소가 담긴 배열..)에 적합하다. 

큰 데이터를 정렬할 때에는 이전 기초 정렬알고리즘보다 더 효율적인 알고리즘이 존재한다. 

 

faster sorts

합병 정렬(merge), 퀵 정렬(quick), 지수 정렬(radix)에 대해서 배워보자 
시간복잡도를 O(n^2)에서O(n log n)으로 바꿀 수 있다.

---

Merge Sort (합병 정렬)

- merging and sorting 의 조합, 정확히 말하자면 분할, 정렬, 합병 모두가 일어난다. 

데이터 배열이 있다고 했을 때 해당 배열이 가장 작은 요소를 갖도록 분할(정렬된 배열이 0개나 1개 요소가 있는 배열이 될 때까지 분할)한다. 

그리고 가장 작은 요소끼리 정렬하며 합친다. 이렇게 합쳐진 배열은 정렬된 상태가 된다. 이 과정을 반복해주면 된다. 

 

 

1-1. 합병 정렬의 합병부분 

정렬된 배열 두 개를 합병시키는 함수를 작성하는 합병 정렬 작성의 첫번째 부분

-> 인자로 받는 배열이 정렬되어 있다고 가정하고 정렬된 배열 두 개의 조합을 반환하기만 하면 된다. 

function merge(arr1, arr2) {
    // 오름차순 정렬(작은수 -> 큰 수 )
    let results = [];
    // ? i와 j는 각각 arr1, arr2의 포인터
    let i = 0;
    let j = 0;
    // ? 첫번째 while문은 하나의 arr가 배열의 끝에 도달하면 끝나버리기 때문에 나머지 요소들을 push해줘야함
    while (i < arr1.length && j < arr2.length) {
      if (arr2[j] > arr1[i]) {
        // arr1[i]가 arr2[j]보다 더 작은 경우는
        // results에 작은 요소를 넣고 i의 포인터를 1증가시켜준다.
        results.push(arr1[i]);
        i++;
      } else {
        results.push(arr2[j]);
        j++;
      }
    }
    // ? 위의 while문에서 result로 넘어가지못하고 남은 요소들을 결과에 담아준다.
    // i와 j의 array 중 어느것이 먼저 배열의 끝에 도달할 지 모르기 때문에 각각 while문 작성
    while (i < arr1.length) {
      results.push(arr1[i]);
      i++;
    }
    while (j < arr2.length) {
      results.push(arr2[j]);
      j++;
    }
    return results;
  }

  merge([1, 10, 50], [2, 14, 99, 100]);

1-2. 합병 정렬의 정렬부분

• 이 부분에서는 재귀함수에 대한 이해가 필요하다. -> 아직 이해하기가 어려워서 개발자 도구를 통해 디버깅을 하면서 콜스택에 어떻게 쌓이는 지 천천히 보면서 이해하려고 했음

// *합병 정렬의 정렬부분
  // ! 목표: 배열을 계속 반으로 나누는 것, 기본케이스의 끝에 도달하여 배열 길이가 1보다 작거나 같아야함(1 or 0)
  // slice() 사용하여 나누는 것을 추천
  // 0 또는 1개의 요소를 가진 작은 배열이 준비되면 작성해놓았던 합병 함수를 사용해 다시 합친다.
  // 재귀함수가 필요하다. => 모든 재귀 함수에는 기본 케이스와 재귀 케이스가 있다는 사실을 기억
  function mergeSort(arr) {
    //기본 케이스 먼저 작성
    if (arr.length <= 1) return arr;
    let mid = Math.floor(arr.length / 2);
    let left = mergeSort(arr.slice(0, mid));
    // ? slice에 start값만 적어주면 end는 자동으로 배열의 끝까지 한다.
    let right = mergeSort(arr.slice(mid));
    return merge(left, right);
  }
  console.log(mergeSort([223, 34, 52, 665, 3]));

merge sort 함수 실행 순서 예시  ref: https://www.udemy.com/course/best-javascript-data-structures/learn/lecture/28560427#overview

📌공부 TIP: 시점마다 호출 스택에 있는 내용을 정확하게 적어보는게 도움이 된다. 아주 긴 배열은 도전하지 마라(어차피 못따라간다.) 위의 이미지처럼 4개정도의 요소를 정렬한다고 생각했을 때 호출스택을 따라가보자 

---

2. 합병 정렬의 시간복잡도

합병 정렬에서 최적, 평균, 최악의 케이스가 모두 O(n log n)으로 같다. 

*공간 복잡도는 O(n)

2-1. 왜 O(n log n)일까?

log n은 증가에 따르는 분할 수이다.  n에 따라 분할할 횟수를 말한다. 배열이 늘어나면 log n 비율로 늘어난다는 것

e.g.)요소가 32개인 배열을 0이나 1이 될 정도로 쪼개려면 5번의 분할이 필요하기 때문에 log n

 

n 은 쪼개놓은 정렬된 요소들을 merge할 때, 배열 요소끼리의 비교 횟수를 말한다. merge를 할 때 각각의 요소끼리 비교하는 과정이 필요하기 때문임  

e.g.) 배열에 요소가 8개가 있다면 결국은 8개의 요소끼리 머지를 할 때 비교를 해야하기 때문에

 

-> 결과적으로 합병 정렬의 시간복잡도는 O(n log n)이 된다. 

 

O(n log n)이 최상의 시간복잡도는 아니지만 데이터(only 숫자 등..)에 구애받지 않는 정렬 알고리즘을 원한다면 최선은 O(n log n)이다. 

 

*공간 복잡도를 다루진 않지만 이전에 배운 3가지 기본 sort 알고리즘에 비해서 합병 정렬이 더 많은 공간을 차지한다.