퀵 정렬

📌 퀵 정렬(Quick Sort)

특정 지점(pivot)을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 이동시킨다.
(자동으로 pivot은 올바른 위치에 놓여짐.)
단일 요소가 될 때까지 위의 과정을 재귀적으로 반복한다.

Pivot Helper

pivot의 선택 위치에 따라 퀵 정렬 실행 시간이 달라질 수 있으므로 pivot을 잘 선택해야 한다.

pivot 설정 기준

: 이상적으로는 데이터 집합의 중간값을 선택한다.
중간값 선택이 어려울 경우에는 첫 번째 요소 / 마지막 요소 / 무작위 요소를 선택한다.

Pivot Helper 함수 구현

1. swap 함수 따로 만들기(자리 바꾸는 기능)
2. pivot을 시작점으로 잡기
3. pivot보다 작은 값이 나오면 swapIdx를 증가시키고, swap하기
4. 반복문을 마친 뒤에 정해진 swapIdx가 pivot의 정확한 위치를 나타내기 때문에 원래 위치에서 swapIdx로 swap하기.

ex. [4,8,2,1,5,7,6,3]

[4,8,2,1,5,7,6,3] -> 2랑 8 swap

[4,2,8,1,5,7,6,3] -> 1이랑 8 swap

[4,2,1,8,5,7,6,3] -> 3이랑 8 swap

[4,2,1,3,5,7,6,8] -> 마지막으로 3이랑 4 swap

[3,2,1,4,5,7,6,8] -> 4가 올바른 위치에 놓여짐.

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

  // We are assuming the pivot is always the first element
  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 the pivot from the start the swapPoint
  swap(arr, start, swapIdx);
  return swapIdx;
}

pivot([4,8,2,1,5,7,6,3])

퀵 정렬 구현

1. pivotIndex를 구해준다.
2. pivotIndex의 왼쪽과 오른쪽에 pivot helper를 재귀적으로 호출한다.
3. 하위 배열의 길이가 1이 되었을 때 재귀를 멈춘다.
   (왼쪽&오른쪽이 일치할 때 길이가 1이 되므로 왼쪽이 오른쪽보다 작을 때까지만 실행.)

과정

 [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

코드

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

  // We are assuming the pivot is always the first element
  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 the pivot from the start the swapPoint
  swap(arr, start, swapIdx);
  return swapIdx;
}


function quickSort(arr, left = 0, right = arr.length -1){
    if(left < right){
        let pivotIndex = pivot(arr, left, right) //3
        //left
        quickSort(arr,left,pivotIndex-1);
        //right
        quickSort(arr,pivotIndex+1,right);
      }
     return arr;
} 
           
quickSort([100,-3,2,4,6,9,1,2,5,3,23])

⭐️ 퀵 정렬의 Big O

시간 복잡도 : O(n log n) ~ O(n^2)

최상의 케이스와 평균적인 케이스에서 O(n log n)이고, 최악의 케이스일 때 O(n^2)이 된다.

• 최악인 케이스 : 다 정렬되어 있는 경우.
  swap이 일어나지 않고 배열을 전부 돌면서 첫 번째 항목만 얻게 된다.
• 이 부분을 개선하려면 pivot을 첫 번째 요소로 정하는 대신 중간이나 마지막, 또는 무작위로 고르면 된다.

공간 복잡도 : O(log n)