CODEWITHSUNDEEP
javascriptsortingcomputer-sciencequicksort
Lapple
Lapple

Reputation: 3373

What is wrong with this QuickSort implementation?

I have the following:

function quickSort(array, low, high) {
    var len = array.length,
        l = low || 0,
        r = high || len - 1,
        m = Math.round((l + r) / 2),
        t;

    do {
        while (array[l] < array[m]) {
            l += 1;
        }
        while (array[r] > array[m]) {
            r -= 1;
        }

        if (l <= r) {
            if (l < r) {
                t = array[r];
                array[r] = array[l];
                array[l] = t;

                console.log('Swapped ' + array[r] + ' with ' +
                                         array[l] + '. ' +
                                         array);
            }

            l += 1;
            r -= 1;
        }
    } while (l <= r);

    if (r > 0) quickSort(array, 0, r);  
    if (l < len - 1) quickSort(array, l, len - 1);
}

Using it as follows:

var initial = [1, 8, 9, 0, 2, 5, 6, 7, 3, 4, 10], // Duplicate, just to compare
    sorted  = [1, 8, 9, 0, 2, 5, 6, 7, 3, 4, 10];

quickSort(sorted);

console.log('Initial: ' + initial + '\nSorted:  ' + sorted);

Surprisingly, the code throws stack_overflow after the array was sorted. I guess I am missing the recursion exit condition, but I don't know where.

Upvotes: 3

Views: 213

Answers (1)

nrabinowitz
nrabinowitz

Reputation: 55688

Edit (replacing previous answer): I believe the issue here is the way you're setting the len variable. For an in-place sort, the len should only be the length of the portion of the array being sorted, not the entire array, or your comparisons at the end will never evaluate to false. So instead of:

var len = array.length,
    l = low || 0,
    r = high || len - 1;

You need to set len based on l and r:

var l = low || 0,
    r = high || array.length - 1,
    len = r-l;

You can see the working jsFiddle here: http://jsfiddle.net/nrabinowitz/PPeh9/6/ - I replaced your test data with a random array for testing.

Upvotes: 3

Related Questions