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:
1 2 3 4 5 6 |
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:
7 8 9 10 11 12 13 14 15 |
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:
16 17 18 19 20 21 22 23 24 |
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:
25 26 27 28 29 30 31 32 33 |
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'} ]; |
相关推荐
JavaScript快速排序递归与非递归实现快速排序概述快速排序(Quiksort)是一种通过基准划分区块并不断交换左右项的排序方式,其采用了分治法,减少了交换
主要介绍了Javascript快速排序算法的相关资料,需要的朋友可以参考下
简述: 用到javascript的排序一组数字,js没有直接的数字比较的函数可以调用,所以自己写了一个快速排序 知识点: 1. 正则表达式提取正负数字的string 2. str 转数字 放回列表 3. js的对象Sort类的声明及定义 4. ...
js代码-JavaScript 快速排序
JavaScript实现的常见排序算法有:冒泡排序,选择排序,插入排序,谢尔排序,快速排序(递归),快速排序(堆栈),归并排序,堆排序。今天我们来详细分析下快速排序算法
主要原理是快速排序的原理:找基准点、建立二个数组分别存储、递归
JavaScript希尔排序、快速排序、归并排序算法_.docx
排序算法(Sorting algorithm)是计算机科学最古老、最基本的课题之一,要想成为合格的程序员,就必须理解和掌握各种排序算法。
快速排序(Quicksort)的Javascript实现
主要介绍了JavaScript实现快速排序的方法,实例分析了javascript快速排序的相关实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下
javascript 实现排序分类功能, 冒泡排序, 快速排序等等
[Ctrl+A 全选 注:如需引入外部Js需刷新才能执行] 代码如下:再你多快,你快不过Array.prototype.sort var a=[4,723,3,5,67,32,4,... 这才是最快的加个二叉树排序 [Ctrl+A 全选 注:如需引入外部Js需刷新才能执行]
主要介绍了基于JavaScript实现的快速排序算法,分析了快速排序的原理并结合实例形式给出了javascript快速排序的操作步骤与相关实现技巧,需要的朋友可以参考下
主要为大家详细介绍了JavaScript希尔排序、快速排序、归并排序算法,感兴趣的朋友可以参考一下
基于javascript的排序算法源码,包括冒泡排序、选择排序、希尔排序、插入排序、快速排序、归并排序、基数排序、堆排序
主要介绍了JavaScript实现快速排序的方法,结合实例形式分析了快速排序的原理、实现方法及相关操作注意事项,需要的朋友可以参考下
js排序算法实现 包括以下算法:冒泡排序 选择排序 插入排序 谢尔排序 快速排序(递归) 快速排序(堆栈) 归并排序 堆排序 从执行时间上可以很直观地看出各种排序的效率