[알고리즘] 퀵 정렬(quick sort)

퀵 정렬(quick sort)

분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속한다.

소개 (오름차순 정렬 기준)

1. 리스트에서 하나의 원소를 고른다. 이 원소를 피벗이라 한다.(보통 가장 작은 인덱스의 요소)
2. 피벗 앞에는 피벗보다 작은 값의 요소를, 피벗 뒤에는 피벗보다 큰 값의 원소가 오도록 리스트를 둘로 나눈다. 이렇게 둘로 나누는 것을 분할이라고 한다.
3. 분할된 두 개의 작은 리스트는 재귀적으로 1~2번 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복한다.

코드

// solution 1 배열 안에서 교환하는 방식
const swap = (idx1, idx2, arr) => {
  let tmp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = tmp;
}

const quickSort = function (arr, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;

  let low = left;
  let high = right;
  let pivot = arr[low];  // 가장 작은 인덱스를 pivot으로 설정

  while (left < right) {
    // 왼쪽부터 pivot 보다 큰 요소를 찾는다.
    while (left < high && arr[left] <= pivot) {
      left++;
    }
    // 오른쪽부터 pivot 보다 작은 요소를 찾는다.
    while (low < right && pivot <= arr[right]) {
      right--;
    }
    // 왼쪽 큰 값 인덱스가 오른쪽 작은 값 인덱스보다 작으면 스왑
    if (left < right) {
      swap(left, right, arr);
    }
  }
  // pivot의 위치 정렬
  swap(low, right, arr)

  // pivot 기준으로 양쪽을 다시 정렬
  quickSort(arr, low, right - 1);
  quickSort(arr, right + 1, high);

  return arr
};

// solution 2 새로운 배열로 분할하는 방식
const quickSort = function (arr) {
  if (arr.length <= 1) return arr;

  let left = [];
  let right = [];
  const pivot = arr[0];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) left.push(arr[i])
    else right.push(arr[i])
  }

  left = quickSort(left, callback);
  right = quickSort(right, callback);

  return [...left, pivot, ...right];
};

장점

• 같은 시간복잡도 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 속도가 빠르다.
• 배열 안에서 교환하는 방식을 사용하면 추가 메모리 공간을 필요로 하지 않는다.

단점

• 불안정 정렬이기 때문에 정렬된 배열에서 오히려 수행시간이 더 걸린다.

정렬 알고리즘 시간 복잡도 비교

---

참고자료

• 위키백과_퀵 정렬
• https://www.digitalocean.com/community/tutorials/js-quick-sort
• https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html