JavaScript Quicksort recursive

Question

I´m trying to implement a quicksort algorithm for an int array in JavaScript. I´ve got a problem in my code. The first few ints get sorted well but at the end of the sortet array there is always one integer which is placed many times although its only one time in the array which should be sorted. Hopefully someone will find my fault. Thanks.

function quicksort(array) {
    var randomPlace = Math.round(Math.random() * array.length);
    var pivotelement = array[randomPlace];
    left = new Array;
    right = new Array;
    for (var i = 0; i < array.length; i++) {
        if (array[i] < pivot) {
            left[left.length] = array[i];
        } else {
            right[right.length] = array[i];
        }
    }
    if ((left.length == 0 || left.length == 1) && (right.length == 0 || right.length == 1)) {
        return left.concat(right);
    } else if (left.length == 0 || left.length == 1) {
        return (left.concat((quicksort(right))));
    } else if (right.length == 0 || right.length == 1) {
        return ((quicksort(left)).concat(right));
    } else {
        return (quicksort(left)).concat((quicksort(right)));
    }
}

Possible duplicate of [JavaScript quicksort](http://stackoverflow.com/questions/5185864/javascript-quicksort) — Liam, Dec 05 '16 at 15:18

score 0 · Answer 1 · edited Dec 04 '19 at 08:07

I think you are identifying the randomPlace wrongly. It returns undefined some times because you're using Math.round().

Try this instead:

var randomPlace = Math.floor(Math.random() * array.length);

Also, use the following code when initializing left, and right:

var left = new Array();
var right = new Array();

Also, you need to change the pivot in array[i] < pivot to pivotElement.

You can see my complete fiddle here

Nina Scholz · Answer 2 · 2016-12-05T17:30:12.383

Beside some nameming confusion, like pivotelement vs pivot and Math.round vs Math.floor, you need to tackle the problem of for example [1, 1, 1] which is always returning left = [] and right = [1, 1, 1], that calls quicksort([1, 1, 1]) ad infinitum.

To overcome this problem, you need to check for empty left and with right every element, if it is equal to the random pivot. Then return right, without calling quicksort again.

function quicksort(array) {
    var randomPlace = Math.floor(Math.random() * array.length),
        pivot = array[randomPlace],
        left = [],
        right = [],
        i;

    for (i = 0; i < array.length; i++) {
        (array[i] < pivot ? left : right).push(array[i]);
    }
    console.log(pivot, JSON.stringify(array), JSON.stringify(left), JSON.stringify(right));

    // prevent looping forever
    if (!left.length && right.every(function (v) { return v === pivot; })) {
        return right;
    }

    if (left.length <= 1 && right.length <= 1) {
        return left.concat(right);
    }
    if (left.length <= 1) {
        return left.concat(quicksort(right));
    }
    if (right.length <= 1) {
        return quicksort(left).concat(right);
    }
    return quicksort(left).concat(quicksort(right));
}

console.log(quicksort([2, 7, 4, 8, 3, 11, 49, 20, 10, 1, 1, 1]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Another solution would be to separate the array into three arrays, one for smaller values, one for equal values and one for greater values. Then sort only the smaller and greater arrays.

function quicksort(array) {
    var randomPlace = Math.floor(Math.random() * array.length),
        pivotValue = array[randomPlace],
        left = [],
        pivot = [],
        right = [],
        i;

    for (i = 0; i < array.length; i++) {
        if (array[i] === pivotValue) {
            pivot.push(array[i]);
            continue;
        }
        (array[i] < pivotValue ? left : right).push(array[i]);
    }

    console.log(pivotValue, JSON.stringify(array), JSON.stringify(left), JSON.stringify(pivot), JSON.stringify(right));

    if (left.length <= 1 && right.length <= 1) {
        return left.concat(pivot, right);
    }
    if (left.length <= 1) {
        return left.concat(pivot, quicksort(right));
    }
    if (right.length <= 1) {
        return quicksort(left).concat(pivot, right);
    }
    return quicksort(left).concat(pivot, quicksort(right));
}

console.log(quicksort([2, 7, 4, 8, 3, 11, 49, 20, 10, 1, 1, 1]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

score 0 · Answer 3 · answered Oct 19 '18 at 20:24

heres a short version of quick sort written in JS exactly as it is seen in Intro To Algorithms, hope this helps!

var partition = function (arr, low, high) {
    var x = arr[high]
    var i = low - 1
    for (var j = low; j <= high - 1; j++) {
        if (arr[j] <= x) {
            i++
            var temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        }
    }
    var temp = arr[i + 1]
    arr[i + 1] = arr[high]
    arr[high] = temp
    return i + 1 
}

var quickSort = function (arr, low, high) {
    if (low < high) {
        index = partition(arr,low,high)
        if (low < index-1) quickSort(arr,low,index-1)
        if (index+1 < high) quickSort(arr,index+1,high)
    }
}

var list2 = [1000,13,12,1001,82,1,2,4,3,0]

console.log(quickSort(list2,0,list2.length))

also on my GitHub

JavaScript Quicksort recursive

3 Answers3