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

Liam
– Liam

2016-12-05 15:18:37 +00:00
Commented Dec 5, 2016 at 15:18 — Liam
– Liam, Commented Dec 5, 2016 at 15:18

Nina Scholz · Accepted Answer · 2016-12-05 17:30:12Z

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; }

Daniel McGrath · Accepted Answer · 2018-10-19 20:24:16Z

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

Community · Accepted Answer · 2019-12-04 08:07:13Z

0

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

edited Dec 4, 2019 at 8:07

CommunityBot

11 silver badge

answered Dec 5, 2016 at 16:02

31piy

23.9k6 gold badges51 silver badges69 bronze badges

Collectives™ on Stack Overflow

JavaScript Quicksort recursive

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related