CFLib.org – quickSort

quickSort(arrayToCompare, sorter)

Last updated January 15, 2012

author

Version: 3 | Requires: ColdFusion MX | Library: UtilityLib

Rated 5 time(s). Average Rating: 3.4

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:

view plain print about

<CFSCRIPT>
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#">

<CFSCRIPT>
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>Unsorted data:</CFOUTPUT>
<CFDUMP VAR="#unsorted#">
<CFSET sorted = quickSort(unsorted, nodeCompare)>
<CFOUTPUT>Sorted data:</CFOUTPUT>
<CFDUMP VAR="#sorted#">

Parameters:

Name	Description	Required
arrayToCompare	The array to be sorted.	Yes
sorter	The comparison UDF.	Yes

Full UDF Source:

	
	
			
			
			
				
				view plain
				
				
				copy to clipboard
				
				
				
				
				print
				
				
				about
				ColdFISH is developed by Jason Delmore.  Source code and license information available at coldfish.riaforge.org.  Version 3.1.1
				
			<!---
 Implementation of Hoare's Quicksort algorithm for sorting arrays of arbitrary items.
 Slight mods by RCamden (added var for comparison).
 Update my Mark Mandel to use List.addAll() functions.
 
 @param arrayToCompare 	 The array to be sorted. (Required)
 @param sorter 	 The comparison UDF. (Required)
 @return Returns a sorted array. 
 @author James Sleeman (&#106;&#97;&#109;&#101;&#115;&#64;&#105;&#110;&#110;&#111;&#118;&#97;&#116;&#105;&#118;&#101;&#109;&#101;&#100;&#105;&#97;&#46;&#99;&#111;&#46;&#110;&#122;) 
 @version 3, January 15, 2012 
--->
<cffunction name="quickSort" hint="Implementation of quicksort" access="public" returntype="array" output="false">
       <cfargument name="arrayToCompare" hint="The array to compare" type="array" required="Yes">
       <cfargument name="sorter" hint="UDF for comparing items" type="any" required="Yes">
       <cfscript>
               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 = arguments.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, arguments.sorter);
               } else {
                       lesserArray = arrayNew(1);
               }

               if (arrayLen(greaterArray)) {
                       greaterArray = quickSort(greaterArray, arguments.sorter);
               } else {
                       greaterArray = arrayNew(1);
               }

               lesserArray.addAll(pivotArray);
               lesserArray.addAll(greaterArray);

               return lesserArray;
       </cfscript>
</cffunction>
		<!---
 Implementation of Hoare's Quicksort algorithm for sorting arrays of arbitrary items.
 Slight mods by RCamden (added var for comparison).
 Update my Mark Mandel to use List.addAll() functions.
 
 @param arrayToCompare      The array to be sorted. (Required)
 @param sorter      The comparison UDF. (Required)
 @return Returns a sorted array. 
 @author James Sleeman (james@innovativemedia.co.nz) 
 @version 3, January 15, 2012 
--->
<cffunction name="quickSort" hint="Implementation of quicksort" access="public" returntype="array" output="false">
       <cfargument name="arrayToCompare" hint="The array to compare" type="array" required="Yes">
       <cfargument name="sorter" hint="UDF for comparing items" type="any" required="Yes">
       <cfscript>
               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 = arguments.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, arguments.sorter);
               } else {
                       lesserArray = arrayNew(1);
               }

               if (arrayLen(greaterArray)) {
                       greaterArray = quickSort(greaterArray, arguments.sorter);
               } else {
                       greaterArray = arrayNew(1);
               }

               lesserArray.addAll(pivotArray);
               lesserArray.addAll(greaterArray);

               return lesserArray;
       </cfscript>
</cffunction>