A reader on my forums asked about sorting structures. His problem was that he had an array of structs and needed to sort by one particular key within each struct.
Here is a simple example of the type of data he wanted to sort:
<cfset d = []>
<cfset d[1] = {name="Ray",rank="234",age="30"}>
<cfset d[2] = {name="Joe",rank="423",age="18"}>
I've got an array with 2 structs. Each struct has the same 'form': name, rank, and age. structSort won't work on this as it required a structure, not an array.
This is where QuickSort comes in. QuickSort is a simple sorting function, but what makes it interesting is that you specify a unique sorting function. This lets you handle any particular type of data you can think of. So given his data, I can write a method that compares two struct nodes:
<cfscript>
function nodeCompare(node1, node2){
if(node1.age lt node2.age) return -1;
if(node1.age eq node2.age) return 0;
if(node1.age gt node2.age) return 1;
}
</cfscript>
The "API" requires that you return -1, 0, and 1 to represent less than, equal to, and greater than, but outside of that, the actual logic is 100% up to you. Assuming that the QuickSort function is already included, here is a complete example:
<cfset d = []>
<cfset d[1] = {name="Ray",rank="234",age="30"}>
<cfset d[2] = {name="Joe",rank="423",age="18"}>
<cfscript>
function nodeCompare(node1, node2){
if(node1.age lt node2.age) return -1;
if(node1.age eq node2.age) return 0;
if(node1.age gt node2.age) return 1;
}
</cfscript>
<cfoutput><b>Unsorted data:</b></cfoutput>
<cfdump var="#d#">
<cfset sorted = quickSort(d, nodeCompare)>
<cfoutput><p><b>Sorted data:</b></cfoutput>
<cfdump var="#sorted#">
And the result:
Ok, so it just plain works. Nice. So I next though - what about arrays of CFCs? I'd assume that would work as well, but I thought I'd give it a try and use it as another excuse to write a script-based CFC in ColdFusion 9.
I designed a super simple person.cfc with 3 properties, and then an init() function to let you quickly set up the object.
component {
property string firstname;
property string lastname;
property string age;
public function init(string firstname, string lastname, numeric age) {
variables.firstname = arguments.firstname;
variables.lastname = arguments.lastname;
variables.age = arguments.age;
}
}
Now that I've that, let's quickly create some people:
<cfset ray = new person('Raymond','Camden',36)>
<cfset jeanne = new person('Jeanne','Camden',35)>
<cfset jacob = new person('Jacob','Camden',9)>
<cfset lynn = new person('Lynn','Camden',7)>
<cfset noah = new person('Noah','Camden',6)>
<cfset family = [ray,jeanne,jacob,lynn,noah]>
This code demonstrates the new keyword, and notice it automatically runs my init function. Now for the sorting. I wrote two sort functions. One to sort by age and one to sort by name:
<cfscript>
function ageCompare(node1, node2){
if(node1.getAge() lt node2.getAge()) return -1;
if(node1.getAge() eq node2.getAge()) return 0;
if(node1.getAge() gt node2.getAge()) return 1;
}
function fNameCompare(node1, node2){
return compare(node1.getFirstName(),node2.getFirstName());
}
</cfscript>
The first function is almost the exact same as my earlier example, but I've switched to calling getAge() on the component. The second function is pretty slim as it just so happens that the CFML compare function returns values in exactly the format we need for QuickSort. Altogether now, I can run my sorts:
<cfset sorted = quickSort(family, ageCompare)>
<cfloop index="p" array="#sorted#">
<cfoutput>#p.getLastName()#, #p.getFirstName()# - #p.getAge()#<br/></cfoutput>
</cfloop>
<p/>
<cfset sorted = quickSort(family, fNameCompare)>
<cfloop index="p" array="#sorted#">
<cfoutput>#p.getLastName()#, #p.getFirstName()# - #p.getAge()#<br/></cfoutput>
</cfloop>
Which gives me:
Camden, Noah - 6
Camden, Lynn - 7
Camden, Jacob - 9
Camden, Jeanne - 35
Camden, Raymond - 36
Camden, Jacob - 9
Camden, Jeanne - 35
Camden, Lynn - 7
Camden, Noah - 6
Camden, Raymond - 36
Nice. To be honest, I think I blogged about QuickSort before so this isn't something new (and I'm sure the computer scientists here will chime in about how it's not as efficient as other sorts ;) but I've always loved how the UDF works. Writing a UDF to use in another UDF just makes me happy all over.