[알고리즘] 퀵 정렬

✅ 퀵 정렬 (Quick Sort)

❕ 기본 개념 

- 분할 정복(divide and conquer) 방법을 통해 정렬

- 수열 안에서 기준이 되는 수인 피봇(pivot)을 임의로 하나 선택한 후, 나머지 수를 '피봇보다 작은 수'와 '피봇보다 큰 수'의 두 그룹으로 나눈다. 피봇을 기준으로 왼쪽과 오른쪽의 리스트들을 각각 정렬하면 전체 정렬이 완료됨

- 분할된 두 개의 리스트에 대해 재귀적으로 앞의 과정을 반복한다. (재귀는 리스트의 크기가 0 또는 1이 될 때까지 반복)

- n의 리스트를 정렬하는데 걸리는 시간을 T(n), c는 임의의 상수라 하고, 리스트가 피봇 기준으로 두개의 비슷한 크기의 부분집합으로 나뉜다는 가정 하에 얻는 평균 시간복잡도는 O(n logn)이다.

- 반면, 운이 나빠 매번 최솟값이 피봇으로 선택되면 모든 숫자가 피봇의 오른쪽으로 가기 때문에 n층의 재귀가 발생하게 됨. 따라서 최악의 경우의 시간복잡도는 O(n²)

 

 

❕ 작동 방식 

 

1 ~ 9 랜덤 수열 퀵 정렬

 

 

[3, 1, 6, 5, 9] 에 대한 퀵 정렬 과정을 나타낸 트리

 

 

 

✔ 구현 방법 (JS) 

function partition(arr, start, end) {
  // Taking the last element as the pivot
  const pivotValue = arr[end];
  let pivotIndex = start;
  for (let i = start; i < end; i++) {
    if (arr[i] < pivotValue) {
      // Swapping elements
      [arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
      // Moving to next element
      pivotIndex++;
    }
  }

  // Putting the pivot value in the middle
  [arr[pivotIndex], arr[end]] = [arr[end], arr[pivotIndex]];
  return pivotIndex;
}

function quickSortRecursive(arr, start, end) {
  // Base case or terminating case
  if (start >= end) {
    return;
  }

  // Returns pivotIndex
  let index = partition(arr, start, end);

  // Recursively apply the same logic to the left and right subarrays
  quickSort(arr, start, index - 1);
  quickSort(arr, index + 1, end);
}

array = [7, -2, 4, 1, 6, 5, 0, -4, 2];
quickSortRecursive(array, 0, array.length - 1);

console.log(array);

// ouput
// -4,-2,0,1,2,4,5,6,7

 

 

참고자료

「알고리즘 도감」 中 2-7 퀵 정렬

Algorithms iOS app - Quick Sort Simulation

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

https://njkhanh.com/quicksort-swift-p5f35363935

https://stackabuse.com/quicksort-in-javascript/