정렬 알고리즘 - 퀵 정렬

August 14, 2022

JavaScript 알고리즘 & 자료구조 마스터 클래스 강의를 듣고 작성하는 강의노트

퀵 정렬 (Quick Sort)

다른 원소와 비교만으로 정렬을 수행하는 비교 정렬이다.
데이터를 분할하여 배열의 원소가 0개 또는 1개의 항목이 남을 때까지 분할하여 개별적으로 정렬되는 방식
피벗 포인트라고 부르는 단일 요소를 선택하여 수행한다.
- 피벗을 기준으로 피벗보다 작다면 왼쪽으로 옮겨지고 크다면 오른쪽으로 옮겨진다.
해당 피벗을 제외하고 왼쪽 리스트와 오른쪽 리스트를 다시 정렬(재귀)한다.

피벗 선택

퀵정렬의 실행시간은 피벗 선택 위치에 따라 달라질 수 있다. 이상적으로는 데이터 집합의 죽안값이 되도록 선택해야 한다. 가능하다면, 데이터 정렬의 중간값을 어떻게 되는지 모른다면 쉽지 않을 것이다. 이에 대한 대안으로 첫 번째 요소, 또는 마지막 요소, 또는 중간, 무작위 요소를 선택한다.

이 문서에서는 간단하게 첫 번째 요소를 피벗으로 삼는다.

피벗 헬퍼 함수

- 이 함수는 배열, 시작인덱스, 끝 인덱스 세 개의 인수를 받는다.
  - 기본값으로 시작 인덱스는 0, 끝 인덱스는 배열 길이 - 1
- 배열 첫번째 요소를 피벗으로 선택한다. (중간, 마지막, 무작위 선택 가능)
- 현재 피벗 인덱스를 변수에 저장한다. (피벗이 끝나는 위치를 추적)
- 시작부터 끝까지 배열 루프를 실행한다.
  - 살펴보는 요소보다 피벗이 클 경우 피벗 인덱스 변수를 증가시킨 후 현재 요소를 피벗 인덱스에 있는 요소로 교환.
  - 시작했던 피벗과 피벗 인덱스를 바꾼 다음 피벗 인덱스를 반환한다.
- 피벗 인덱스 반환

function pivot(arr, start = 0, end = arr.length + 1) {
  // swap
  function swap(array, i, j) {
    let temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
 
  let pivot = arr[start];
  let swapIdx = start;
 
  for (let i = start + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }
  swap(arr, start, swapIdx);
  return swapIdx;
}
 
pivot([4, 8, 2, 1, 5, 7, 6, 3]);

1회전 [4, 8, 2, 1, 5, 7, 6, 3] arr[i] 8, swapIdx 0
2회전 [4, 2, 8, 1, 5, 7, 6, 3] arr[i] 2, swapIdx 1, 2 와 8 교환
3회전 [4, 2, 1, 8, 5, 7, 6, 3] arr[i] 1, swapIdx 2, 8 과 1 교환
4회전 [4, 2, 1, 8, 5, 7, 6, 3] arr[i] 5, swapIdx 2
5회전 [4, 2, 1, 8, 5, 7, 6, 3] arr[i] 7, swapIdx 2
6회전 [4, 2, 1, 8, 5, 7, 6, 3] arr[i] 6, swapIdx 2
7회전 [4, 2, 1, 3, 5, 7, 6, 8] arr[i] 3, swapIdx 3, 3 과 8 교환

swap(arr, 0, 3);
피벗(4)과 swapIdx 위치의 값(3)을 교환
결과: [3, 2, 1, 4, 5, 7, 6, 8]
      ^        ^

퀵 정렬 구현

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

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right); // 위에서 정의한 헬퍼 함수 사용
    quickSort(arr, left, pivotIndex - 1); // left
    quickSort(arr, pivotIndex + 1, right); // right
  }
}
 
quickSort([4, 8, 2, 1, 5, 7, 6, 3]);

빅오(Big O)

시간복잡도

Best Complexity	Average Complexity	Worst Complexity
O(n log n)	O(n log n)	O(n²)

공간 복잡도

Space Complexity
O(log n)