trying to write quick sort algorithm without making 2 new lists and appending, cannot figure out what is problem

user_18430253 0
Viewed 78

Just got into coding and have tried several hours to figure out why I would not get a terminal output. Any guesses?

const unsortedArray = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9];
let initialIndex, finalIndex, i, j;

function quickSort(initialIndex, finalIndex, unsortedArray) {
    if(initialIndex >= finalIndex) {
        return unsortedArray;
    }

    let key = initialIndex;
    let i = initialIndex + 1;
    let j = finalIndex;

    while(i <= j) {

        while (unsortedArray[i]<=unsortedArray[key] && i<finalIndex) {
            i++;
        }
        
        while (unsortedArray[j]>=unsortedArray[key] && j>initialIndex) {
            j--;
        }
    
        if(i > j) {
            let temp = unsortedArray[initialIndex];
            unsortedArray[initialIndex] = unsortedArray[j];
            unsortedArray[j] = unsortedArray[initialIndex];
        } else {
            let temp = unsortedArray[i];
            unsortedArray[i] = unsortedArray[j];
            unsortedArray[j] = temp;
        }
        
    }
    quickSort(initialIndex,j-1,unsortedArray);
    quickSort(j+1,finalIndex,unsortedArray);
    return unsortedArray
}

function showSortedArray (unsortedArray) {
    quickSort(0, unsortedArray.length-1, unsortedArray);
    console.log(unsortedArray);
}

showSortedArray(unsortedArray);

I have found other ways (creating two new array and appending left and right), but I want to succeed in this method.

quicksort javascript
2 Answers

Your function is going into an infinite loop whenever both i and j equal the finalIndex value.

The problem is this line here:

    while (unsortedArray[i]<=unsortedArray[key] && i<finalIndex) {
        i++;
    }

Because you have i<finalIndex, i is never getting to finalIndex, which it should because it's a valid value that may need to be swapped (this is in contrast to the key/initialIndex value which is the pivot/bound and is handled differently).

You could change it to this:

while (unsortedArray[i]<=unsortedArray[key] && i<=finalIndex) {

But now you'll get an array out-of-bounds error after it passes finalIndex, so instead you need to change it to this:

while (i<=finalIndex && unsortedArray[i]<=unsortedArray[key]) {

So now it will check the array limit first, before trying to access the array. This should fix your problems.

user_1091220

The simplest quicksort I've managed to find is this:

function quicksort(arr)
{
    if (arr.length == 0)
        return [];
 
    var left = []
    var right = []
    var pivot = arr[0];
 
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
           left.push(arr[i]);
        } else {
           right.push(arr[i]);
        }
    }
 
    return quicksort(left).concat(pivot, quicksort(right));
}

And a version for 2D arrays:

function quicksort_2D(options)
{
    /*
        options:
            arr     - arr to sort
            sortcol     - column position to sort on
            sorttype    - 
    */

    if (options.arr.length == 0)
        return [];
 
    var left = []
    var right = []
    var pivot = options.arr[0][options.sortcol];
 
    for (var i = 1; i < options.arr.length; i++) {
        if (options.arr[i][options.sortcol] < pivot) {
            left.push(options.arr[i]);
        } else {
            right.push(options.arr[i]);
        }
    }
    var pivotarr=[options.arr[0]]
    
    var retval = quicksort_2D({arr: left, sortcol: options.sortcol, sorttype: options.sorttype}).concat(pivotarr, quicksort_2D({arr: right, sortcol: options.sortcol, sorttype: options.sorttype}));
    return retval
}
user_18277640
Related