> -----Original Message-----
> From: Richard White [mailto:[EMAIL PROTECTED]
> Sent: Monday, November 06, 2006 4:32 PM
> To: CF-Talk
> Subject: Re: sort algorithm
>
> hi, just wondering if anyone had any thought on the above. Thanks
This comes with a caveat... I can't remember if it works. ;^)
It's from a while ago (I was building a CFML version of my JavaScript
collection object). It's a CFML version of Hoare's QuickSort algorithm. I
could swear I fully tested this but I don't have an environment to testing
this instant.
You basically pass it an array and a function that will compare two elements
of that array in format of:
SortFunction(Element1, Element2)
That function needs to return either a "1" (if the first element is greater
than the second), "0" (if the two elements are equal) or "-1" (if the first
element is less than the second).
This means that your work is greatly simplified (you only need to compare
two elements) and the quickSort function does all of the actual sorting
work.
Give it a shot - let me know if fails and I'll take a look.
Jim Davis
<cffunction name="quickSort"
hint="Method to sort collection members using
Hoare's QuickSort algorithm."
access="private"
output="no"
returntype = "Array">
<!--- Input Arguments --->
<cfargument name="ArrayToSort" type="Array" required="Yes"
hint="An array of identically typed
components to be sorted." />
<cfargument name="Tester" type="any" required="Yes"
hint="The function which will compare the
elements of the passed array." />
<!--- Set Local Scope --->
<cfset var local = StructNew() />
<!--- Set the local variables --->
<cfset local.LowerArray = ArrayNew(1) />
<cfset local.UpperArray = ArrayNew(1) />
<cfset local.PivotArray = ArrayNew(1) />
<cfset local.TestResult = "" />
<!--- Initialize the pivot Array --->
<cfset local.PivotArray[1] = arguments.ArrayToSort[1] />
<!--- If the problem has become trival (only one elemet
left) return --->
<cfif ArrayLen(arguments.ArrayToSort) LT 2>
<cfreturn arguments.ArrayToSort />
</cfif>
<!--- Loop over the array and assign elements to the
appropriate array --->
<cfset local.CurArrayLen = ArrayLen(arguments.ArrayToSort) />
<cfloop from="2" to="#local.CurArrayLen#" index="local.Cnt">
<!--- Determine the relative positon of the current
two elements using the Comparator function --->
<cfset local.TestResult =
arguments.Tester(arguments.ArrayToSort[local.Cnt], local.PivotArray[1]) />
<!--- Based on the comparison build the lower and
upper arrays --->
<cfswitch expression="#local.TestResult#">
<cfcase value="1">
<cfset ArrayAppend(local.UpperArray,
arguments.ArrayToSort[local.Cnt]) />
</cfcase>
<cfcase value="0">
<cfset ArrayAppend(local.PivotArray,
arguments.ArrayToSort[local.Cnt]) />
</cfcase>
<cfcase value="-1">
<cfset ArrayAppend(local.LowerArray,
arguments.ArrayToSort[local.Cnt]) />
</cfcase>
</cfswitch>
</cfloop>
<!--- If needed sort the lower array --->
<cfif ArrayLen(local.LowerArray)>
<cfset local.LowerArray = quickSort(local.LowerArray,
arguments.Tester) />
</cfif>
<!--- If needed sort the upper array --->
<cfif ArrayLen(local.UpperArray)>
<cfset local.UpperArray = quickSort(local.UpperArray,
arguments.Tester) />
</cfif>
<!--- Append the pivot array to the lower array --->
<cfset local.CurArrayLen = ArrayLen(local.PivotArray) />
<cfloop from="1" to="#local.CurArrayLen#" index="local.Cnt">
<cfset ArrayAppend(local.LowerArray,
local.PivotArray[local.Cnt]) />
</cfloop>
<!--- Append the upper array to the lower array --->
<cfset local.CurArrayLen = ArrayLen(local.UpperArray) />
<cfloop from="1" to="#local.CurArrayLen#" index="local.Cnt">
<cfset ArrayAppend(local.LowerArray,
local.UpperArray[local.Cnt]) />
</cfloop>
<!--- Return the fully sorted array --->
<cfreturn local.LowerArray />
</cffunction>
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|
Introducing the Fusion Authority Quarterly Update. 80 pages of hard-hitting,
up-to-date ColdFusion information by your peers, delivered to your door four
times a year.
http://www.fusionauthority.com/quarterly
Archive:
http://www.houseoffusion.com/groups/CF-Talk/message.cfm/messageid:259399
Subscription: http://www.houseoffusion.com/groups/CF-Talk/subscribe.cfm
Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=89.70.4
