퀵 정렬 알고리즘의 개념

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

퀵 정렬 알고리즘의 특징

퀵 정렬은 재귀적으로 정의되므로 재귀 호출에 따른 스택이 사용된다. 이때 스택의 깊이는 n개의 원소에 대해 logn에 비례하므로 공간복잡도는 O(nlogn)이다. 따라서 in-place 정렬이라고 하기 힘들지만, 실용적으로는 상대적으로 작은 메모리만을 사용하므로 흔히 in-place 정렬이라고 기술하기도 한다.

퀵 정렬은 최약의 경우 pivot이 배열 내에서 가장 작은 값 또는 가장 큰 값으로 설정된다면 원소 n개에 대해서 n번, (n-1)번, (n-2)번 … 1번의 비교가 필요하므로 시간복잡도가 최대 O(n^2) 이 된다.

하지만 평균 시간 복잡도는 O(nlogn) 으로 매우 빠르다. pivot 값이 적절히 설정된다면 그 속도는 매우 빠르다.

따라서 pivot값을 잘 설정하는 것이 중요하다.

퀵 정렬은 중복된 키 값이 순서대로 바뀌지 않을 수 있어 not-stable 하다.

(예를들어 [7, 7, 1]을 오름차순으로 퀵 정렬 수행)

코드

// arr: [3, 6, 8, 10, 1, 2, 1]
function quickSort(arr) {
	const len = arr.length;
  if (len <= 1) return arr;
  const pivot = arr[parseInt(len / 2)];
  const left = arr.filter((x) => x < pivot);
  const middle = arr.filter((x) => x === pivot);
  const right = arr.filter((x) => x > pivot);
  return [...quickSort(left), ...middle, ...quickSort(right)];
}

// result: [1, 1, 2, 3, 6, 8, 10]