问题描述:

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.

网友答案:

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

  • How to sort this array with hashes?
  • https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/sort

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.

相关阅读:
Top