// JavaScript 구현
function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left >= right) return;

    // 파티셔닝 수행 후 피벗의 최종 위치를 받음
    const pivotIndex = partition(arr, left, right);

    // 피벗을 기준으로 좌/우 재귀 정렬
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
    
    return arr;
}

function partition(arr, left, right) {
    const pivot = arr[right]; // 가장 오른쪽 요소를 피벗으로 선택
    let i = left - 1;

    for (let j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            // arr[i]와 arr[j] 교환
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    
    // 마지막으로 피벗을 제자리에 둠
    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
    return i + 1;
}

const arr = [5, 3, 8, 4, 9, 1, 6];
console.log("초기 배열:", arr);
quickSort(arr);
console.log("정렬 결과:", arr);