🚀 Quick Sort

高速ソートは分割征服法を用いた典型的なアルゴリズムであり,平均O(nlogn)の時間的複雑さを有する.
高速ソートでpivotをどのように設定するかは、効率と安定性に依存します.
これは、配列とインデックス(左、右、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;
}