본문 바로가기
카테고리 없음

[JS] 퀵정렬, 병합정렬과의 비교

by 해룸 2024. 5. 12.

1. 소개

퀵정렬이란 pivot(중심축)을 정하고, 중심축 보다 작은 값들은 왼쪽으로, 큰 값들은 오른쪽으로 보내는것이다.

pivot을 정해 왼쪽 오른쪽으로 나누고 다시금 왼쪽 오른쪽에 대해 재귀적으로 pivot을 정해 왼쪽 오른쪽을 나누고.. 이 과정을 반복하다보면 결국 정렬이 완성 된다.

 

2. 작동개념

  • 분할: 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분배열로 분할한다.
  • 정복: 부분배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.
  • 결합: 정렬된 부분 배열들을 하나의 배열에 합병한다.
  • 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는것을 보장할 수 있다.

 

3. 시간복잡도

평균적으로 O(n log2 n) 실행시간을 가지는 매우 빠른 정렬 방법 중 하나이다. 

그러나 이미 정렬된 배열을 첫번째 원소를 기준으로 퀵 정렬하는 경우는 최악의 시나리오 이며, O(n^2) 실행시간을 가진다.

 

4. 구현

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];
};

 

5. 퀵 정렬과 병합 정렬

공통점

  • 분할정복 알고리즘에 속한다.
  • 평균적으로 O(n log n)의 성능을 갖는다.
  • 둘 다 점점 탐색할 배열의 크기를 쪼개어 재귀함수에 넘겨준다.

차이점

  • 병합정렬은 배열을 분할하는 방식이 반으로 쪼개는것
  • 퀵 정렬은 크게 두가지의 분할방법이 있다.(1. 배열의 마지막값을 pivot으로 2. 배열의 중간값을 pivot으로)
  • 퀵정렬은 병합정렬과 달리 메모리 공간을 사용하지 않는다.
    (오직 재귀 콜 스택을 위한 메모리만 사용됨, 그에 비해 병합정렬은 매 번 새로운 배열을 만들어 내므로 메모리 사용량이 더 큼)
  • 병합정렬은 stable하지만, 퀵 정렬은 unstable 하다.