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.
