Pivot

pivot이라는 helper함수를 만들어 줄 것 입니다
배열의 첫번 째 값을 기준값으로 두고
왼쪽에는 작은 값 오른쪽에는 큰 값을 두었을때 기준값이 처음 배열에서 몇 번재 인덱스 자리에 이썽야하는지를 반환합니다

코드로 보겠습니다

function pivot(arr, start = 0, end = arr.length - 1) {
  function swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  let pivot = arr[start];
  let swapIndex = start;

  for (let i = start + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      swapIndex++;
      swap(arr, swapIndex, i);
    }
  }
  swap(arr, start, swapIndex);
  return swapIndex;
}

예시로 pivot이라는 함수가 어떻게 동작하는지 설명 드리겠습니다
예시는 [4,6,7,2,1,5,9,3] 배열로 하겠습니다

현재의 pivot값으로 첫번째 값 4 저장해둡니다
swapIndex를 인자로 들어오는 start로 둡니다

루프를 시작하여
pivot값이 arr[i]값 보다 크다면 swapIndex을 올린뒤 swap합니다
루프가 끝나면 pivot이 있어야할 위치인 swapIndex와 swap합니다

차근차근 값이 어떻게 움직이는 지 보겠습니다

1. 기준값은 첫번째 값인 4로 시작합니다
2. 루프를 시작합니다
3. 2는 4보다 작으니 swapIndex을 1 올려주고 6과 자리를 바꿔 줍니다
   [4,2,7,6,1,5,9,3]
4. 1은 4보다 작으니 swapIndex을 1 올려주고 7과 자리를 바꿔 줍니다
   [4,2,1,6,7,5,9,3]
5. 3은 4보다 작으니 swapIndex을 1 올려주고 6과 바꿔줍니다
   [4,2,1,3,7,5,9,6]
6. 루프가 종료되어 swapIndex와 start index 자리를 swap합니다
   [3,2,1,4,7,5,9,6]

QuickSort

코드로 먼저 보겠습니다

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

pivot helper 함수를 이용하여 첫번째 값이 어디 index으로 가야할지 구합니다
그 값을 기준으로 앞 뒤로 나누어 정렬을 게속하게됩니다
위의 로직이 계속 실행되어 정렬된 arr배열을 반환하게 됩니다