퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)이란?

기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다.

퀵 정렬 과정

1. 데이터를 분할하는 pivot을 설정한다. 이 경우 pivot의 위치는 임의로 설정해도 된다.
2. pivot을 기준으로 데이터를 2개의 집합으로 분리한다.

• 이때 pivot의 왼쪽에는pivot보다 작은 수, 오른쪽에는 큰 수를 놓는다.

3. 분리 집합에서 다시 pivot 을 선정한다.
4. 분리 집합이 1개 이하가 될 때까지 위의 과정을 반복한다.

퀵 정렬의 시간 복잡도

평균적인 시간 복잡도는 O(nlogn)이고, 최악의 경우 O(n^2)이다.

코드

function quickSort(arr) {
  
  //base case
  if(arr.length < 2) 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 if (arr[i] > pivot) {
      right.push(arr[i]);
    } else {
      pivot.push(arr[i]);
    }
  }
return quickSort(left).concat(pivot, quickSort(right));
}