Stable quicksort in Javascript
October 28th, 2008
Firefox < v3.0 doesn't have a stable Array.sort() function - that is, it doesn't maintain indexes for elements of equal value. This is undefined in the ECMA spec, and has been fixed in Firefox as of version 3 (and curiously enough has been stable in IE all along). As a result, I set out to find a stable, efficient Array.sort() replacement/supplement.
Mergesort is famous for being stable by design, and fast, though not terribly memory efficient. However, it uses a lot of code, and I couldn't manage to find a stable implementation of it.
After doing a little homework, I decided to modify this quicksort pseudocode to get the results I was after. Some would argue that quicksort's worst case performance is slower than mergesort, but for my purposes (small datasets) this was moot.
Here is the resulting code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | // STABLE implementation of quick sort to replace unstable Array.sort method in Firefox quickSort = function(arr) { // return if array is unsortable if (arr.length <= 1){ return arr; } var less = Array(), greater = Array(); // select and remove a pivot value pivot from array // a pivot value closer to median of the dataset may result in better performance var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; // step through all array elements for (var x = 0; x < arr.length; x++){ // if (current value is less than pivot), // OR if (current value is the same as pivot AND this index is less than the index of the pivot in the original array) // then push onto end of less array if ( (arr[x] < pivot) || (arr[x] == pivot && x < pivotIndex) // this maintains the original order of values equal to the pivot ){ less.push(arr[x]); } // if (current value is greater than pivot), // OR if (current value is the same as pivot AND this index is greater than or equal to the index of the pivot in the original array) // then push onto end of greater array else { greater.push(arr[x]); } } // concatenate less+pivot+greater arrays return quickSort(less).concat([pivot], quickSort(greater)); }; |
Of course, this will only sort an array of values (strings, numbers), so to sort an array of objects by a given property, I modified the above to produce:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | // STABLE implementation of quick sort to replace unstable Array.sort method in Firefox // if sorting an array of objects, key = name of object property to compare // otherwise leave key undefined quickSort = function(arr, key) { // return if array is unsortable if (arr.length <= 1){ return arr; } var less = Array(), greater = Array(); // select and remove a pivot value pivot from array // a pivot value closer to median of the dataset may result in better performance var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; // step through all array elements for (var x = 0; x < arr.length; x++){ // if (current value is less than pivot), // OR if (current value is the same as pivot AND this index is less than the index of the pivot in the original array) // then push onto end of less array if ( ( !key // no object property name passed && ( (arr[x] < pivot) || (arr[x] == pivot && x < pivotIndex) // this maintains the original order of values equal to the pivot ) ) || ( key // object property name passed && ( (arr[x][key] < pivot[key]) || (arr[x][key] == pivot[key] && x < pivotIndex) // this maintains the original order of values equal to the pivot ) ) ){ less.push(arr[x]); } // if (current value is greater than pivot), // OR if (current value is the same as pivot AND this index is greater than or equal to the index of the pivot in the original array) // then push onto end of greater array else { greater.push(arr[x]); } } // concatenate less+pivot+greater arrays return quickSort(less, key).concat([pivot], quickSort(greater, key)); }; |
Code samples
Now we can define an array of objects such as:
var objects = [ {id: 1, type: 'fruit', name: 'apple', color: 'yellow'}, {id: 2, type: 'vegetable', name: 'tomato', color: 'red'}, {id: 3, type: 'fruit', name: 'apple', color: 'red'}, {id: 4, type: 'vegetable', name: 'pepper', color: 'red'} ];
Then sort by color with a call to:
objects = quickSort(objects, 'color'); // sorted objects = [ {id: 2, type: 'vegetable', name: 'tomato', color: 'red'}, {id: 3, type: 'fruit', name: 'apple', color: 'red'}, {id: 4, type: 'vegetable', name: 'pepper', color: 'red'}, {id: 1, type: 'fruit', name: 'apple', color: 'yellow'} ];
Then sort by type:
objects = quickSort(objects, 'type'); // sorted objects = [ {id: 3, type: 'fruit', name: 'apple', color: 'red'}, {id: 1, type: 'fruit', name: 'apple', color: 'yellow'}, {id: 2, type: 'vegetable', name: 'tomato', color: 'red'}, {id: 4, type: 'vegetable', name: 'pepper', color: 'red'} ];
Then sort by name:
objects = quickSort(objects, 'name'); // sorted objects = [ {id: 3, type: 'fruit', name: 'apple', color: 'red'}, {id: 1, type: 'fruit', name: 'apple', color: 'yellow'}, {id: 4, type: 'vegetable', name: 'pepper', color: 'red'}, {id: 2, type: 'vegetable', name: 'tomato', color: 'red'} ];
elegant and very useful. Thank you.
Elegant and every useful. Thanks acat!
[...] 下面参照网上的资料（这里和这里），用Javascript语言实现上面的算法。 [...]
[...] 下面参照网上的资料（这里和这里），用Javascript语言实现上面的算法。 [...]
[...] 下面参照网上的资料（这里和这里），用Javascript语言实现上面的算法。 [...]
[...] reference to the data on the net (belowhereandhere), with Javascript language realization of the above [...]
[...] 下面参照网上的资料（这里和这里），用Javascript语言实现上面的算法。 [...]