🚀 Quick Sort

퀵정렬은 분할정복법을 쓰는 대표적인 알고리즘이며, 평균적으로 O(nlogn)의 시간복잡도를 갖는다.

퀵정렬에서는 pivot을 어떻게 설정하느냐에 따라 효율성과 안정성이 달라진다.

배열과 인덱스(left, right, pivot)를 매개변수로하는 분할함수를 재귀호출하는 방식이다.

분할함수에서는 인덱스를 한칸씩 옮겨가며 swap을 통해 값을 정렬한다.

⌨ 구현 코드

function quickSort(array, left = 0, right = array.length - 1) {
    if(left >= right) return;

    const mid = Math.floor((right - left) / 2);
    const pivot = array[mid];
    const partition = divide(array, left, right, pivot);

    //재귀호출 (분할정복)
    quickSort(array, left, partition - 1);
    quickSort(array, partition, right);

    //배열을 둘로 나눈 후 오른쪽 배열의 left index값 리턴
    function divide(array, left, right, pivot) {
        while(left <= right) {
            //pivot 보다 작은 값은 swap skip
            while(array[left] < pivot) {
                left++;
            }
        
            //pivot 보다 큰 값은 swap skip
            while(pivot < array[right]) {
                right--;
            }

            //swap (pivot 보다 큰 left의 값과 pivot보다 작은 right의 값)
            if(left <= right) {
                let swap = array[left];
                array[left] = array[right];
                array[right] = swap;
                //한칸씩 옮기기
                left++;
                right--;
            }
        }

        return left;
    }

    return array;
}