[javascript]quick-sort - ver2 (median, left, right)pivot

( 너무나도 꼰대적인 교수 한명 때문에 이번 학기는 정말이지 너무나도 스트레스 받는다. )

 

 

파라메터로 넘겨주는 값에 따라 pivot의 위치가 변하는 퀵소트

function swap(list, from, to) {
    const dummy = list[to];
    list[to] = list[from];
    list[from] = dummy;
}

function findMedian(list, left, mid, right) {
    let median = right;
    if (list[left] > list[mid] && list[mid] < list[right]) {
        median = mid;
    } else if (list[mid] > list[right] && list[right] < list[left]) {
        median = right;
    } else if (list[mid] > list[left] && list[left] < list[right]) {
        median = left;
    }

    return median;
}

function partition(list, left, right, mode) {
    let row = left;
    let high = right;
    let mid = Math.floor((left + right) / 2);
    console.log(mid)
    let pivot;
    let pivot_value;
    if (mode === "m") {
        pivot = findMedian(list, left, mid, right);
        pivot_value = list[pivot];
    } else if (mode === "l") {
        pivot = left;
        pivot_value = list[pivot];
    } else {
        pivot = right;
        pivot_value = list[pivot];
    }

    while (row < high) {
        if(pivot === left || pivot === right){
            while (list[row] <= pivot_value && row < high)
                row++;
            while (list[high] >= pivot_value && high >= row)
                high--;
        }else if(pivot === mid){
            while (list[row] <= pivot_value && row <= high)
                row++;
            while (list[high] > pivot_value && high >= row)
                high--;
        }
        if (row >= high)
            break;

        swap(list, row, high);
        }
        if (pivot === left) {
            swap(list, pivot, high);
            return high;
        } else if (pivot === right) {
            swap(list, pivot, high + 1);
            return high;
        }else if(pivot === mid){
            return high;
        }

    }

    function quickSort(list, left, right, mode) {
        if (left < right) {
            const pivot = partition(list, left, right, mode);
            console.log(left, right)
            // console.log(pivot)
            quickSort(list, left, pivot, mode);
            quickSort(list, pivot + 1, right, mode);
        }
    }
    //option 
    //'l' == leftPivot
    //'r' == rightPivot
    //'m' == median
   	
    const array = [30, 1,4, 1,10,56, 2, 30,102,804, 4,20, 20,172,26,390, 7,12 ,10,2];
    quickSort(array,0,array.length-1,'m');
    console.log(array);

 

quickSort 함수의 4번째로 넣어주는 char에 따라 pivot의 위치가 배열의 왼쪽 , 중간 값, 오른쪽으로 변한다. 왼쪽과 오른쪽을 피벗으로 설정하여 , 퀵소트를 실행하는 것은 간단하나, 중간 값을 이 퀵소트를 최대한 변화시키지 않고, 활용하기는 조금 힘들었다. 중간 값 피벗은 배열의 맨 왼쪽과  맨 오른쪽, 중간에 위치한 값 중 값이 2번째로 높은 것을 피벗으로 설정하는데, 좌측 일수도 , 중간 일수도 , 우측 일수도 있기에 이때 설정된 피벗의 위치에따라 swap의 조건이 달라진다.