Problem with QuickSort algorithm causing Maximum Call Stack

Question

So, I have a program that calls the function : doQuickSort that takes the array i want sorted. I used a quicksort algorithm and everything seems fine to me but when returning the Partitionindex at the bottom of the Partition function I exceed the stack calls. If anyone can help me that would be great.

const animations = [];

export const swap = (arr, current, next) =>{

    animations.push(arr[current]);
    animations.push(arr[next]);

    var curVal = arr[current];
    arr[current] = arr[next];
    arr[next] = curVal;
}

export const doQuickSort = (array) => {
    var run = 0; 
    
    if(run == 0){
        QuickSort(array, 0, array.length-1);
        run++;
    }

    function partition(array, start, end){
        let pivot = array[end];
        let partitionIndex = start;
        
        for(let i = start; i < end; i++){
            if(array[i] <= pivot){
                swap(array, i, partitionIndex);
                partitionIndex++;
            }
        }

        swap(array, partitionIndex, end);
        partitionIndex++;

        return partitionIndex;
    }

    function QuickSort(array, start, end){
        if(start < end){
            let partitionIndex = partition(array, start, end);
            QuickSort(array, start, partitionIndex-1);
            QuickSort(array, partitionIndex+1, end);
        }
    }

    return array;
}

Novy · Accepted Answer · 2020-11-16 22:57:08Z

I do not really understand your "partitionIndex++;" before the "return partitionIndex; " inside the partition method. IMO that is your problem. OK your animations array inside the swap method also is bizarre for me. You probably have your reason for it.

But try this by the way:

const animations = [];

const swap = (arr, current, next) =>{

    animations.push(arr[current]);
    animations.push(arr[next]);

    var curVal = arr[current];
    arr[current] = arr[next];
    arr[next] = curVal;
}

const doQuickSort = (array) => {
    var run = 0; 
    
    if(run == 0){
        QuickSort(array, 0, array.length-1);
        run++;
    }

    function partition(array, start, end){
        let pivot = array[end];
        let partitionIndex = start;
        
        for(let i = start; i < end; i++){
            if(array[i] <= pivot){
                swap(array, i, partitionIndex);
                partitionIndex++;
            }
        }

        swap(array, partitionIndex, end);
        //partitionIndex++;

        return partitionIndex;
    }

    function QuickSort(array, start, end){
        if(start < end){
            let partitionIndex = partition(array, start, end);
            QuickSort(array, start, partitionIndex-1);
            QuickSort(array, partitionIndex+1, end);
        }
    }

    return array;
}

console.log(doQuickSort([5,3,7,6,2,9]))

Collectives™ on Stack Overflow

Problem with QuickSort algorithm causing Maximum Call Stack

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related