퀵 정렬도 합병 정렬과 비슷하게 재귀함수를 사용하여 구현합니다

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배열을 반환하게 됩니다