Created
July 22, 2014 03:06
-
-
Save adohe-zz/e82d197960959aee0b16 to your computer and use it in GitHub Desktop.
Quick Sort algorithm implementation in JavaScript
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (function() | |
| { | |
| var | |
| defaultCompare, | |
| defaultSwap, | |
| partition, | |
| quickSort; | |
| Array.prototype.quickSort = function(compare, swap) | |
| { | |
| if (typeof compare !== "function") | |
| { | |
| compare = defaultCompare; | |
| } | |
| if (typeof swap !== "function") | |
| { | |
| swap = defaultSwap; | |
| } | |
| quickSort(this, 0, this.length - 1, compare, swap); | |
| }; | |
| defaultCompare = function(value1, value2) | |
| { | |
| return value1 < value2; | |
| }; | |
| defaultSwap = function(array, index1, index2) | |
| { | |
| var temp = array[index1]; | |
| array[index1] = array[index2]; | |
| array[index2] = temp; | |
| }; | |
| partition = function(array, start, stop, compare, swap) | |
| { | |
| var pivot = array[stop], storeIndex = start - 1; | |
| while (start < stop) | |
| { | |
| if (compare(array[start], pivot)) | |
| { | |
| storeIndex++; | |
| swap(array, storeIndex, start); | |
| } | |
| start++; | |
| } | |
| swap(array, storeIndex + 1, stop); | |
| return storeIndex + 1; | |
| }; | |
| quickSort = function(array, startIndex, stopIndex, compare, swap) | |
| { | |
| var pivot, stack, start, top; | |
| stack = new Array(stopIndex - startIndex + 1); | |
| top = -1; | |
| stack[++top] = startIndex; | |
| stack[++top] = stopIndex; | |
| while (top > -1) | |
| { | |
| stopIndex = stack[top--]; | |
| startIndex = stack[top--]; | |
| pivot = partition(array, startIndex, stopIndex, compare, swap); | |
| if (pivot - 1 > startIndex) | |
| { | |
| stack[++top] = startIndex; | |
| stack[++top] = pivot - 1; | |
| } | |
| if (pivot + 1 < stopIndex) | |
| { | |
| stack[++top] = pivot + 1; | |
| stack[++top] = stopIndex; | |
| } | |
| } | |
| }; | |
| }()); | |
| // Plain Sort | |
| var plainSort = [4, 7, 6, 5, 0, 1, 5]; | |
| plainSort.quickSort(); | |
| console.log(JSON.stringify(plainSort)); | |
| // | |
| //Sort With Custom Compare Function | |
| // | |
| var descendingOrder = [4, 7, 6, 5, 7, 0, 1, 5, 10, 10, 8]; | |
| descendingOrder.quickSort(function(a, b) | |
| { | |
| //Descending order compare | |
| return a > b; | |
| }); | |
| console.log(JSON.stringify(descendingOrder)); | |
| // Sort multiple arrays with a custom compare | |
| var table = | |
| { | |
| "employeeName": ["Jane", "John", "Tom", "Alex", "Mary"], | |
| "id": [10, 5, 7, 3, 0] | |
| }; | |
| table.employeeName.quickSort(function(a, b) | |
| { | |
| //Strings have to be compared using the localeCompare function | |
| return (a || "").localeCompare(b) < 0; | |
| }, | |
| function(array, index1, index2) | |
| { | |
| //Sorts both arrays in the 'table' object | |
| var temp = array[index1]; | |
| array[index1] = array[index2]; | |
| array[index2] = temp; | |
| temp = table.id[index1]; | |
| table.id[index1] = table.id[index2]; | |
| table.id[index2] = temp; | |
| }); | |
| console.log(JSON.stringify(table)); | |
| //Prints:{"employeeName":["Alex","Jane","John","Mary","Tom"],"id":[3,10,5,0,7]} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment