QuickSort in Javascript - error too much recursion

Question

I've created my own custom quicksort routine to work with a custom data structure I have. It should work just like a regular quicksort except that for comparisons I need use a special function to convert strings into numeric values.

Anyways I must have done something wrong because Firefox tells me "error too much recursion".

Here is the code:

//Will be called on various buckets to sort by dates
function target_sort_wrapper(array) {
    target_sort(array, array.length, 0, length-1);
}

//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);
    //recursive calls now - left then right
    target_sort(array, pivotIndex, 0, pivotIndex - 1);
    target_sort(array, array.length - (pivotIndex+1), pivotIndex+1, array.length - 1);
}

function partition(array, pivotIndex, left, right) {
    //first, put the pivot as the first element to make things easier
    swap(array, pivotIndex, 0);
    var pivot = array[0];
    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)) {
            swap(array, i, j);
            i = i + 1; 
        }
    }
}

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

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Thanks for any help.

I don't mean to be rude, but by the time you get to your 143rd question one would think that the process of correctly formatting code would be pretty familiar. — Pointy
– Pointy, Commented Jul 23, 2012 at 21:06
could you please format it so that it's easier to read? hint: jsfiddle.net — Yoeri
– Yoeri, Commented Jul 23, 2012 at 21:06
Why do you have a random pivot? Why you can't use the default Array's sort function? — davidbuzatto
– davidbuzatto, Commented Jul 23, 2012 at 21:08
@davidbuzatto: Using a random pivot is an acceptable method that helps protect against pathological cases like pre-sorted data. — mellamokb
– mellamokb, Commented Jul 23, 2012 at 21:09
Your recursive calls are not correct. But you knew that already. :). Strongly suggest looking at en.wikipedia.org/wiki/Quicksort. In particular, the first recursive call isn't using 'left', and it probably should. The second recursive call isn't properly computing the length of the chunk to sort, nor is it properly using left or right. — dyoo
– dyoo, Commented Jul 23, 2012 at 22:50

Community · Accepted Answer · 2017-05-23 12:21:13Z

1

To do a custom sort, you can use a "compare function". Take a look:

Although you have a good question, you don't need to implement your sorting algorithm or be concerned about it, just use what I said.

edited May 23, 2017 at 12:21

CommunityBot

11 silver badge

answered Jul 23, 2012 at 21:24

davidbuzatto

9,4841 gold badge48 silver badges52 bronze badges

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

2 Comments

JDS Over a year ago

Thanks for the response, upvoted. However my main interest here is actually the implementation of quicksort, I'm sad to say I've never really done it. So I was hoping to figure out what's wrong with my logic.

davidbuzatto Over a year ago

@YoungMoney: ok, no problem. I thought that your problem was just to sort the array. See ya!

Collectives™ on Stack Overflow

QuickSort in Javascript - error too much recursion

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related