Tag: 불안정 정렬

문제를 세분화하는 분할 정복(divide and conquer)과 퀵 정렬

퀵 정렬은 하나의 중심(pivot) 값을 기준으로 큰 값과 작은 값을 분류하고 이 작업을 반복하여 정렬하는 방법이다.

그림으로 보면 다음과 같다.

첫 요소인 6을 기준으로 잡아서 이보다 작은 수를 left, 큰 수를 right로 분류하고 이 작업을 세분화해서 반복 진행하면 최종적으로 정렬된 배열을 반환할 수 있다.

const quickSort = (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]);
    }
  }
  return [...quick(left), pivot, ...quick(right)]
}

console.log(quickSort([6,3,5,1,9,4,8,2,7]));

퀵 정렬은 최악의 경우를 제외하면 O(NlogN)의 시간 복잡도를 갖는 속도가 장점이지만 단점은 최악의 경우(이미 정렬된 배열) 시간 복잡도가 O(N^2)로 대폭 증가하고 불안정 정렬(unstable sort, 동일한 값에 대해서는 순서가 바뀔 수 있음)이라는 점이다.