📋 퀵 정렬 알고리즘

이 포스팅에서 알아볼 퀵 정렬은 1960년에 찰스 앤터니 리처드 호어가 개발한 방법으로 이후 많은 사람들이 수정 보완하여 완성된 정렬 알고리즘이다.

이 알고리즘은 처음 소개된 이후로 반세기가 넘었지만 현존하는 가장 빠른 정렬 알고리즘 중 하나이다.

대부분의 상황에서 가장 빠른 정렬 알고리즘인 퀵 정렬의 작동방식부터 살펴보자.

---

📌 1. 퀵 정렬 작동 방식

https://visualgo.net/en/sorting

우선 pivot값을 정하고 그 pivot값을 기준으로 배열을 나눈다.
해당 사진에선 배열의 첫 번째 요소를 pivot값으로 정했다.

한 쪽에는 기준점보다 작은 항목들이 위치하고 다른 쪽에는 기준점보다 큰 항목들이 위치한다.

나뉘어진 하위 배열에 대해 재귀적으로 퀵 정렬을 호출하여 모든 배열이 기본 배열(요소가 하나뿐인 배열)이 될 때까지 반복하면 정렬이 완료된다.

---

📌 2. 퀵 정렬 구현

function pivot(arr, start = 0) {
  function swap(array, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  let pivot = arr[start];
  let swapIdx = start;
  for (var i = start + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }

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

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left);
    //left
    quickSort(arr, left, pivotIndex - 1);
    //right
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

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

---

📌 3. 퀵 정렬의 시간 복잡도

퀵 정렬의 최악의 경우의 시간 복잡도는 O(n^2) 이고 평균 복잡도는 O(n log n) 이다.

퀵 정렬의 시간 복잡도는 어떻게 pivot을 선정하는지에 따라 갈린다.

만약 이미 정렬된 배열이 있다고 가정해보자.
이미 정렬되어있는 배열에서 첫 번째 인덱스를 pivot으로 정하면 pivot이 n에 도달할때까지 비교연산이 계속 진행되기 때문에 시간 복잡도는 n-1 * n 이 되어서 O(n^2) 가 되게된다.