Pat asks:
As Pat mentions, there is indeed an arraySort function built into ColdFusion, but it sorts single dimension arrays only. One way of handling this is with a bubble sort implementation. I found a good example of this on Nathan Stanford's site. Here is a quick example:Is there an easy way to 'sort' a two dimensional array ? I know you can use ArraySort() on a single dimensional array.
For example: I have a two dimensional array that has a reference number in element 1 (which refers to a supplier in a database), in element 2 is a calculated distance from a supplied postcode. The array is produced in the order that suppliers are retrieved from the database. However, it would be better to sort the array by distance before outputting the data.
<cfset data = arrayNew(2)>
<cfset data[1][1] = "Alpha">
<cfset data[1][2] = 9>
<cfset data[2][1] = "Beta">
<cfset data[2][2] = 1>
<cfset data[3][1] = "Gamma">
<cfset data[3][2] = 12>
<cfdump var="#data#">
<cfloop index="outer" from="1" to="#arrayLen(data)#">
<cfloop index="inner" from="1" to="#arrayLen(data)-1#">
<cfif data[inner][2] gt data[outer][2]>
<cfset arraySwap(data,outer,inner)>
</cfif>
</cfloop>
</cfloop>
<cfdump var="#data#">
You will notice the code is rather simple. We loop over the array with an outer and inner loop, doing comparisons as we run through the data. If you read the wikipedia article you will see that this sort isn't the best for large sets of data. Another option then would be to simply create the data into a query. You probably had the data in a query already. If not, you can make one with queryNew. At that point, the sorting becomes a trivial matter of using a query of query.
Archived Comments
Ray your post inpired me to write some thought of representing sets of objects in two-dimensional arrays vs. arrays-of-structs vs. query objects.
I also included a UDF for sorting an array of structures on multiple keys, each key with it's own sort order. <a href="http://martijnvanderwoud.wo... a look</a> if you're interested!
Martijn van der Woud
messed up the url, sorry. The correct one is http://martijnvanderwoud.wo...
Ray,
I have trying to implement MergeSort to sort a collection of objects (Name/Value objects with CompareItem method), but haven't quite got it working. The code is based on pseudo code from wikipedia and is provided below. I still not sure where the error is, once it is done I will try to post to CFLib.
<code>
<!--- Method: MergeSort --->
<!--- based on pseudo code from http//en.wikipedia.org/wiki/Merge... --->
<cffunction name="ArrayMergeSort" access="private" output="false" returntype="Array">
<cfargument name="PassedArray" type="Array" required="true" />
<!--- Method variables --->
<cfset var LeftArray = ArrayNew(1) />
<cfset var RightArray = ArrayNew(1) />
<cfset var ReturnArray = ArrayNew(1) />
<cfset var Middle = 0 />
<cfset var i = 1 />
<!--- Method implementation --->
<cfscript>
// if length is 1, return array
if(ArrayLen(arguments.PassedArray) LTE 1) {
ReturnArray = Arguments.PassedArray;
} else {
// Find middle
middle = Int(ArrayLen(arguments.PassedArray)/2);
step = "Calculated Middle as Value #middle#";
// Append elements less than or equal to middle to left array
for(i=1;i LTE middle;i = i+1){
ArrayAppend(LeftArray,Arguments.PassedArray[i]);
}
// Append elements greater than middle to right array
for(i=middle+1;i LTE ArrayLen(arguments.PassedArray);i=i+1){
ArrayAppend(RightArray,Arguments.PassedArray[i]);
}
// Recursively call ArrayMergeSort on partitioned arrays
LeftArray = ArrayMergeSort(LeftArray);
RightArray = ArrayMergeSort(RightArray);
// Merge arrays
ReturnArray = ArrayMerge(LeftArray,RightArray);
}
</cfscript>
<!--- Method Return --->
<cfreturn ReturnArray />
</cffunction>
<!--- Method: Merge --->
<!--- based on pseudo code from http//en.wikipedia.org/wiki/Merge... --->
<cffunction name="ArrayMerge" access="private" output="false" returntype="Array">
<cfargument name="PassedArray1" type="Array" required="true" />
<cfargument name="PassedArray2" type="Array" required="true" />
<!--- Method variables --->
<cfset var ReturnArray = ArrayNew(1) />
<cfset var LeftArray = Arguments.PassedArray1 />
<cfset var RightArray = Arguments.PassedArray2 />
<cfset var i = 1 />
<!--- Method implementation --->
<cfscript>
// Loop through arrays until all items are removed from either
// the left or right array and added to return array
while(ArrayLen(LeftArray) GT 0 AND ArrayLen(RightArray GT 0)) {
// if left item is less than right, then add to return array
// Note: uses compareItem() method of NameValueItem
if(LeftArray[1].compareItem(RightArray[1]) LTE 0) {
ArrayAppend(ReturnArray,LeftArray[1]);
ArrayDeleteAt(LeftArray,1);
} else {
// otherwise, add right item to return array
ArrayAppend(ReturnArray,RightArray[1]);
ArrayDeleteAt(RightArray,1);
}
}
// If elements remain in Left array, append them to return array
if(ArrayLen(LeftArray) GT 0) {
for(i=1;i LTE ArrayLen(LeftArray);i = i +1) {
ArrayAppend(ReturnArray,LeftArray[i]);
}
}
// If elements remain in Right array, append them to return array
if(ArrayLen(RightArray) GT 0) {
for(i=1;i LTE ArrayLen(RightArray);i = i +1) {
ArrayAppend(ReturnArray,RightArray[i]);
}
}
</cfscript>
<!--- Method return --->
<cfreturn ReturnArray />
</cffunction>
</code>
@Martin - Cool stuff - thanks for sharing that.
@Thomas - Wow, your comment is bigger than my blog entry. ;) Normally I ask folks to _not_ paste giant blocks of code in.
Sorry about that Ray. I will try to be better in the future.
Just found this blog post: http://antcooper.com/2008/0...
It contains a UDF to do a merge-sort (presumably faster than bubble sort or insertion sort) on an array of structures, on one key. I haven't tried it yet but it could be useful for large datsets.
I never can remember the syntax for this thanks!
I've made some improvements to my UDF. It is now capable of sorting arrays of beans (CFC's), as well as structures. It is available at http://martijnvanderwoud.wo...
Hmm, I wonder if this is still an issue in CF 10, now that you can pass in a callback function to arraySort()? Seems like you could use that to do a recursive sort for multidimensional arrays.
@tc I actually spent a ton of time implementing a mergeSort algorithm in CF recently, only to replace it with arraySort. I just did a quick search of cflib.org and didn't see your mergeSort on there. Maybe I should post mine?
Correct - arraySort in CF10 would let you pass a closure- making this simpler.