[JS] Merge & Quick Sort 구현하기

1. 병합정렬(Merge Sort)

• 전체 데이터를 분할한 뒤 다시 병합하면서 정렬

• 장점
  어떠한 경우에도 좋은 성능을 보장
  중복된 데이터의 순서가 바뀌지 않는 stable

• 단점
  30 개 이하의 숫자를 정렬할 때는 삽입 정렬과 별 차이가 없음
  정렬하는데 추가 메모리가 필요함 (in-place 알고리즘이 아님)

성능

• Best Case : $O(nlog(n))$
• Worst Case: $O(nlog(n))$
• Average Case : $O(nlog(n))$

구현코드

function mergeSort(array) {
  if (array.length < 2) {
    return array;
  }
  let pivot = Math.floor(array.length / 2);
  let left = array.slice(0, pivot);
  let right = array.slice(pivot, array.length);
  return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }
  return result;
}

2. 퀵정렬(Quick Sort)

• pivot을 잡아 좌측에는 작은 값, 우측에는 큰 값으로 정렬
  리스트의 크기가 0이나 1이 될때까지 반복

• 장점
  in-place 알고리즘으로 메모리 공간 절약

• 단점
  중복값들의 위치가 변할 수 있는 unstable한 정렬

성능

• Best Case : $O(nlog(n))$
• Worst Case: $O(n^2)$
• Average Case : $O(nlog(n))$

구현코드

const quickSort = function (arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] <= pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }

  const lSorted = quickSort(left);
  const rSorted = quickSort(right);
  return [...lSorted, pivot, ...rSorted];
};