Coding the QuickSort algorithm - output not quite right

Question

I've never coded this myself before, unfortunately. My implementation operates on a custom class based on sorting the "date" field. Yes I am fully aware I can use the built-in Javascript sort and specify the comparator function but that's not what I'm interested in.

Currently I start with a reverse-sorted list, and then after calling my "target_sort" (QuickSort), I get a not-very-well sorted list.

Code:

function target_sort_wrapper(array) {
    target_sort(array, array.length, 0, array.length);
}


//Quicksort to swap around targets based on dates
//"array" is DDATA, where DDATA[i] are targets
function target_sort(array, length, left, right) {
    if (length < 2) {
        return;
    }
    var pivotIndex = choosePivot(array, length); //returns the index    

    partition(array, pivotIndex, left, right);

    target_sort(array, pivotIndex, 0, pivotIndex - 1);
    target_sort(array, pivotIndex, pivotIndex + 1, array.length);

}

function partition(array, pivotIndex, left, right) {
    //first, put the pivot as the first element to make things easier
    array.swap(pivotIndex, 0);
    var pivot = array[0];
    var i = left + 1;
    for (var j = left + 1; j < right; j++) {
        if (dateValue(array[j].date) < dateValue(pivot.date)) {
            //dateValue converts stuff like "Jun18" into 618, to numerically compare
            array.swap(i, j);
            i = i + 1;
        }
    }
    //don't forget to put pivot back where it belongs
    array.swap(left, i - 1);
}

function choosePivot(array, length) {
    return Math.floor(Math.random() * length); //0 (inclusive) to length (exclusive) 
}

    Array.prototype.swap = function (i, j) {
        var temp = this[i];
        this[i] = this[j];
        this[j] = temp;
        return this;
    }

And here is the output. First the reverse-sorted list is printed, followed by the result of my "target_sort":

Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 
============================================================= 
Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun25 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun25 Jun25 Jun25 Jul05 Jun25 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jun25 Jul06 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jul06 Jul06 Jun25 Jul06 Jun25 Jun25 Jun25 Jun25 Jul05 Jun25 Jul05 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul05 Jul05 Jul05 Jul06

I feel like it's getting there, but something is still off.

I've been stuck on this for a few days now, so much thanks for any help.

Cheers.

What's codereview? Is it somewhere more appropriate to ask my question? — JDS
– JDS, Commented Jul 24, 2012 at 19:49
@YoungMoney Yes. They can verify your code there. codereview.stackexchange.com — user586399
– user586399, Commented Jul 24, 2012 at 19:51
@Desolator: CodeReview is for code that is working that you want to see if you can improve. This code is not working, so StackOverflow is the proper site for it. — Ken White
– Ken White, Commented Jul 24, 2012 at 19:54

Karoly Horvath · Accepted Answer · 2012-07-24 20:13:39Z

7

The recursive call is broken:

target_sort(array, pivotIndex, 0, pivotIndex - 1);

One obvious thing is that you pass pivotIndex as length for both partitions which doesn't make any sense.

The other one is that indexing is broken. As you can see the left index is 0, but that clearly won't be true if you on the second recursion level and want to get the left partition of an upper level right partition.

One more thing: the pivot chooser doesn't have to know about the array:

function choosePivot(length)

Hint: Programming is not a guessing game, before you start, decide what your "variables" exactly mean. What's lenght, left, right? For example: Is the right index inclusive (does it point to a part of the partition or just beyond it). Then pick a paper and pencil and figure out the proper indexes and lengths. Trust me, the more carefully you think about it, the quicker you'll finish. Debugging wastes a lot of time. Then, just to verify that you are on the right track use a small toy array for your implementation, and add some console.log messages to see what's going on.

edited Jul 24, 2012 at 20:13

answered Jul 24, 2012 at 19:55

Karoly Horvath

96.8k11 gold badges123 silver badges181 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

JDS Over a year ago

Thanks for the input. So the right-half recursive call should have length (array.length - pivotIndex - 1) I think, just from drawing it out. However now I get the error "too much recursion" and the program crashes. And I'm not sure what should be the left index if it's not 0?

Karoly Horvath Over a year ago

for your last question: well, what's the left index of the partition? also, see update.

JDS Over a year ago

That's the thing, I think the left half I want to call quicksort on will always be from 0 to my old pivotIndex...

JDS · Accepted Answer · 2012-07-24 22:15:43Z

I have created a correct version now, thank you to Karoly for the hints. Summary:

Should not do stuff with respect to length, but wrt left and right
I was always picking a bad pivot for the recursive calls (again, must be wrt left and right, and must fall within the proper range of the subarray)

Code:

function target_sort_wrapper(array) {
    target_sort(array, 0, array.length);
}


//Quicksort to swap around targets based on dates
//"array" is DDATA, where DDATA[i] are targets
function target_sort(array, left, right) {
    if ((right-left) < 2) {
        return;
    }

    var pivotIndex = choosePivot(left, right); //returns the index  

    pivotIndex = partition(array, pivotIndex, left, right);

    target_sort(array, left, pivotIndex);
    target_sort(array, pivotIndex+1, right);

}

function partition(array, pivotIndex, left, right) {
    //first, put the pivot as the first element to make things easier
    var pivot = array[pivotIndex];
    array.swap(pivotIndex, left);
    var i = left + 1; 
    for(var j = left + 1; j < right; j++) {
        //if (array[j] > pivot) { } //do nothing, satisfies invariant
        if (dateValue(array[j].date) < dateValue(pivot.date)) {
        //if (array[j] < pivot) {
            array.swap(i, j);
            i = i + 1; 
        }
    }
    //don't forget to put pivot back where it belongs
    array.swap(left, i-1);
    return (i-1);
}

function choosePivot(left, right) {
    return (left + Math.floor(Math.random() * (right-left)));

}

Array.prototype.swap = function(i, j) {
    var temp = this[i];
    this[i] = this[j];
    this[j] = temp;
    return this;
}

Collectives™ on Stack Overflow

Coding the QuickSort algorithm - output not quite right

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related