[JS 알고리즘] 퀵 정렬(Quick Sort)

퀵 정렬 원리

• 퀵 정렬은 기본적으로 재귀를 사용해서 데이터를 쪼개고, 배열이 0개나 1개의 요소를 가지면 각자 정렬된 배열이 된다는 점을 이용해서 정렬을 했던 병합 정렬과 같은 가정에서 출발한다.

  • 그렇지만 병합정렬과는 약간 다르다. 피봇 포인트라고 부르는 기준점을 선택하여 작업을 한다. 해당 숫자보다 작은 숫자를 모두 왼쪽으로 옮기고, 그 숫자보다 큰 숫자들은 모두 오른쪽으로 옮기는 일이다.

• 퀵 정렬은 분할정복 방법을 통해 리스트를 정렬한다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

• 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

피벗 헬퍼 함수

• 병합 정렬을 구현하려면 먼저 피벗의 양쪽에 있는 배열의 요소를 배열하는 기능을 담당하는 함수를 구현하는 것이 유용하다.

• 피벗보다 작은 모든 값을 피벗의 왼쪽으로 이동시키고, 피벗보다 큰 모든 값을 피벗의 오른쪽으로 이동하도록 배열의 요소를 재정렬한다.
  - 피벗의 양쪽에 있는 요소의 순서는 중요하지 않다.

• 헬퍼함수는 새 배열을 만들지 않고 기존 배열에 대해서 작업을 한다.

• 완료되면 헬퍼 함수는 피벗의 인덱스를 반환한다.

• 피벗 선택

  • 퀵 정렬의 런타임은 부분적으로 피벗을 선택하는 방법에 따라 다르다.
  • 피벗을 정렬 중인 데이터 세트의 대략 중앙값이 되도록 설정하면 이상적이다.
  • 이번에는 단순화를 위해 피벗을 첫 번째 요소로 선택한다.

피벗 헬퍼 함수 코드(JS)

- 배열, 시작 인덱스 및 끝 인덱스의 세 가지 인수를 받아들이는 데 도움이 됩니다(각각 기본값은 0이고 배열 길이는 1이 될 수 있음)
- 배열의 시작 부분에서 피벗을 잡습니다.
- 현재 피벗 인덱스를 변수에 저장합니다(피벗이 끝나는 위치를 추적합니다).
- 처음부터 끝까지 배열을 반복합니다.
- 피벗이 현재 요소보다 크면 피벗 인덱스 변수를 증가시킨 다음 현재 요소를 피벗 인덱스에 있는 요소로 바꿉니다.
- 시작 요소(예: 피벗)를 피벗 인덱스로 교체
- 피벗 인덱스 반환

function pivot(arr, start = 0, end = arr.length - 1) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

  // 피봇이 항상 첫 번째 요소라고 가정
  let pivot = arr[start];
  let swapIdx = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }

  swap(arr, start, swapIdx);
  return swapIdx;
}

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

/* for 루프
[4, 8, 2, 1, 5, 7, 8, 3]  i 1, arr[1] 8, swapIdx 0
[4, 2, 8, 1, 5, 7, 8, 3]  i 2, arr[2] 2, swapIdx 1 (8), 2<->8
[4, 2, 1, 8, 5, 7, 8, 3]  i 3, arr[3] 1, swapIdx 2 (8), 1<->8 
[4, 2, 1, 8, 5, 7, 8, 3]  i 4, arr[4] 5, swapIdx 2
[4, 2, 1, 8, 5, 7, 8, 3]  i 5, arr[5] 7, swapIdx 2
[4, 2, 1, 8, 5, 7, 8, 3]  i 6, arr[6] 8, swapIdx 2
[4, 2, 1, 3, 5, 7, 8, 8]  i 7, arr[7] 3, swapIdx 3(8), 3 <-> 8

swap(arr, 0, 3)
[3, 2, 1, 4, 5, 7, 8, 8] 3<->4 */

퀵 정렬 코드 구현 (JS)

- 배열에서 피벗 도우미 호출
- 피벗 헬퍼 함수가 업데이트된 피벗 인덱스를 반환하면 해당 인덱스의 왼쪽에 있는 하위 배열과 해당 인덱스의 오른쪽에 있는 하위 배열에서도 피벗 헬퍼 함수를 재귀적으로 호출한다.
- 이러한 작업은 요소가 2개 미만인 하위 배열에서 발생한다.

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right); // 위에서 정의한 헬퍼 함수 사용
    // left
    quickSort(arr, left, pivotIndex - 1);
    // right
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

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

퀵 정렬의 성능

• 시간 복잡도
  • Best case , average case: $O(nlogn)$
    • 퀵정렬도 병합정렬처럼 $log_2n$ 만큼의 decompostion(분할) 작업을 해야 한다. 예를 들어 32개 요소가 있는 경우에는 절반씩 계속 나누어 1개의 요소씩으로 파편화하는데 5번($log_232$)번의 분할을 해야 한다.
    • 이렇게 매 분할마다 n번의 비교를 해야 한다.
  • worst case : $O(n^2)$
    • 만약 이미 정렬이 되어 있는 배열을 퀵정렬하고, 선택된 pivot이 항상 가장 작은 값이라면 (가장 큰 값이거나), 모든 요소에 대해 n번의 분할을 하고 매번 모든 요소에 대해 n번의 비교를 해서, $n^2$의 시간이 걸린다.
      • 따라서 pivot으로 지금까지 했던 것처럼 첫 번째 요소를 선택하는 대신에 무작위(또는 가운데)로 요소를 선택하는 방식으로 상기 문제를 피할 수 있다. 이렇게 하면 정렬된 배열이라고 할지라도 문제 발생을 피할 확률을 높일 수 있다.
• 공간 복잡도 : $O(logn)$

(추가) 퀵 정렬 구현 코드 다른 버전 (JS)

function 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 quickSort(left).concat(pivot, quickSort(right)); 
}

  const data = [50, 100, 38, 48, 58, 29, 38, 49];
  console.log(quickSort(data));