QuickSort(arrayToCompare, sorter)
Last updated March 12, 2002
Version: 1 | Requires: ColdFusion 5 | Library: UtilityLib
Description:
Using this UDF you are able to sort an array via the Quicksort algorithm using your own comparison function to enable you to sort arrays of anything (simple variables, structs, arrays, dates...).
Your sort UDF must return one of three values: -1 if the first value is less than the second. 0 if the values are equal. 1 if the first value is greater than the second.
Return Values:
Returns a sorted array.
Example:
function nodeCompare(node1, node2){
if(node1.display lt node2.display) return -1;
if(node1.display eq node2.display) return 0;
if(node1.display gt node2.display) return 1;
}
function node() {
var newStruct = structNew();
newStruct.Display = RandRange(100, 200000);
return newStruct;
}
</CFSCRIPT>
<CFSET unsorted = arrayNew(1)>
<CFLOOP FROM="1" TO="10" INDEX="arID">
<CFSET unsorted[arID] = node()>
</CFLOOP>
<CFOUTPUT><B>Unsorted data:</B></CFOUTPUT>
<CFDUMP VAR="#unsorted#">
<CFSET sorted = quickSort(unsorted, nodeCompare)>
<CFOUTPUT><P><B>Sorted data:</B></CFOUTPUT>
<CFDUMP VAR="#sorted#">
Parameters:
Name | Description | Required |
---|---|---|
arrayToCompare | The array to be sorted. | Yes |
sorter | The comparison UDF. | Yes |
Full UDF Source:
<cfscript>
/**
* Implementation of Hoare's Quicksort algorithm for sorting arrays of arbitrary items.
* Slight mods by RCamden (added var for comparison)
*
* @param arrayToCompare The array to be sorted.
* @param sorter The comparison UDF.
* @return Returns a sorted array.
* @author James Sleeman (james@innovativemedia.co.nz)
* @version 1, March 12, 2002
*/
function quickSort(arrayToCompare, sorter){
var lesserArray = ArrayNew(1);
var greaterArray = ArrayNew(1);
var pivotArray = ArrayNew(1);
var examine = 2;
var comparison = 0;
pivotArray[1] = arrayToCompare[1];
if (arrayLen(arrayToCompare) LT 2) {
return arrayToCompare;
}
while(examine LTE arrayLen(arrayToCompare)){
comparison = sorter(arrayToCompare[examine], pivotArray[1]);
switch(comparison) {
case "-1": {
arrayAppend(lesserArray, arrayToCompare[examine]);
break;
}
case "0": {
arrayAppend(pivotArray, arrayToCompare[examine]);
break;
}
case "1": {
arrayAppend(greaterArray, arrayToCompare[examine]);
break;
}
}
examine = examine + 1;
}
if (arrayLen(lesserArray)) {
lesserArray = quickSort(lesserArray, sorter);
} else {
lesserArray = arrayNew(1);
}
if (arrayLen(greaterArray)) {
greaterArray = quickSort(greaterArray, sorter);
} else {
greaterArray = arrayNew(1);
}
examine = 1;
while(examine LTE arrayLen(pivotArray)){
arrayAppend(lesserArray, pivotArray[examine]);
examine = examine + 1;
};
examine = 1;
while(examine LTE arrayLen(greaterArray)){
arrayAppend(lesserArray, greaterArray[examine]);
examine = examine + 1;
};
return lesserArray;
}
</cfscript>
Search CFLib.org
Latest Additions
Andy Jarrett added
listWithNullsToA...
1 day(s) ago
Craig Kaminsky added
verifyEmail
6 day(s) ago
Rob Brooks-Bilson added
Magic8Ball
7 day(s) ago
anthony petruzzi added
parseExcel
7 day(s) ago
Nathan Mische added
REStructFindValu...
9 day(s) ago
Top Rated
QueryStringChang...
Rated 5.0, 10 time(s)
formToNameValueP...
Rated 5.0, 5 time(s)
HTMLSafe
Rated 5.0, 4 time(s)
viewCSS
Rated 5.0, 4 time(s)
generateRandomKe...
Rated 5.0, 4 time(s)