퀵 정렬

퀵 정렬은 배열 내에서 무작위로 숫자를 하나 선택하고 그걸 기준(피벗)으로 잡는다. 그리고 나머지 숫자들을 비교하여 피벗보다 큰 숫자는 피벗의 오른쪽으로, 작은 숫자들은 피벗의 왼쪽으로 이동시킨다. 퀵 정렬도 병합 정렬처럼 분할 정복 패턴과 재귀를 사용한 방식이다.

퀵 정렬을 실행하면 배열은 다음과 같이 정렬된다.

[피벗보다 작은 숫자] < 피벗(기준이 되는 숫자) < [피벗보다 큰 숫자]

이제 피벗을 기준으로 이동한 피벗보다 작은 숫자와, 피벗보다 큰 숫자들은 다시 하나의 숫자가 남을 때까지 재귀를 사용하여 퀵 정렬을 반복하면 된다.

퀵 정렬은 피벗을 기준으로 나뉜 두 자식 배열에서 다시 피벗을 선정하여 그 자식이 숫자 하나로만 이루어진 자식이 될 때까지의 과정을 log₂n번 반복하여 정렬한다. 그리고 각 단계에서는 숫자와 피벗을 1번만 비교하기 때문에 각 단계에서는 O(n)의 시간 복잡도를 가진다.

따라서 퀵 정렬은 평균적으로 병합 정렬과 비슷한 시간 복잡도를 가지지만, 이미 정렬된 배열 혹은 랜덤으로 피벗을 선택할 때 가장 작은 수(혹은 가장 큰 숫자)를 순서대로 고르게 된다면 모든 단계에서 모든 숫자들이 한 쪽으로 이동하기 때문에 재귀가 n번 발생하여 최악의 경우 시간 복잡도는 O(n²)이 나올 수 있다.

/**
 *
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @returns number[]
 */
function merge(arr1, arr2) {
  let answer = [];
  let i = 0;
  let j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      answer.push(arr1[i]);
      i++;
    } else {
      answer.push(arr2[j]);
      j++;
    }
  }

  while (i < arr1.length) {
    answer.push(arr1[i]);
    i++;
  }

  while (j < arr2.length) {
    answer.push(arr2[j]);
    j++;
  }

  return answer;
}

/**
 * @param {number[]} arr
 * @returns number[]
 */
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);
}

console.log(mergeSort([1, 53, 23, 92, 54, 111]));