QuickSort in ColdFusion, with a ColdFusion 9 example as well

This post is more than 2 years old.

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.

Raymond Camden's Picture

About Raymond Camden

Raymond is a senior developer evangelist for Adobe. He focuses on document services, JavaScript, and enterprise cat demos. If you like this article, please consider visiting my Amazon Wishlist or donating via PayPal to show your support. You can even buy me a coffee!

Lafayette, LA https://www.raymondcamden.com

Archived Comments

Comment 1 by Brenda posted on 7/19/2009 at 8:07 PM

Thanks Ray! I was looking for a similar function all week to help sort an array of structs passed from a C++ function.

Comment 2 by Ben Nadel posted on 7/19/2009 at 8:12 PM

Good stuff Ray. Don't worry about efficiencies. When computer scientist jump in with this sorting algorithm is better than that one, it's purely at the theoretical level. They rarely stop and realize that we're sorting small arrays where orders of magnitude in efficiencies can't even be felt in testing :) This is what my guidance counselor in college told me is the difference between Computer Engineers and Computer Scientists.

Comment 3 by Elliott Sprehn posted on 7/20/2009 at 4:02 PM

@Ray

Hmm, seems you should read about sorting algorithms. ;)

QuickSort is O(n log n) and that's as efficient as it gets for comparison based sorting. If you picked the worst pivot every time you could get O(n^2) but that doesn't happen in practice.

Surprised there's no MergeSort on cflib.

@Ben

That's a pretty silly thing to say! Algorithms are quite important. You take for granted every day that someone chose the right algorithm.

We walk on the shoulders of giants every day. Sometimes it's easy to forget the work they did because they did their job so well we don't notice until it's broken.

Comment 4 by Ben Nadel posted on 7/20/2009 at 4:07 PM

@Elliott,

Sorry, I didn't mean to imply that algorithm choice was not to be taken seriously. All I meant was that at the small scale, which is where I think a lot of work, it doesn't make much of a difference. Obviously, the larger the sets of data get, the more important algorithm choice becomes.

Comment 5 by Raymond Camden posted on 7/20/2009 at 4:53 PM

See Ben, I _told_ you the computer scientists would jump on me. ;)

@Elliott: If you want to submit a MergeSort, that would be sweet.

Comment 6 by leeahoward posted on 9/28/2015 at 3:07 PM

The quicksort udf you are using here doesn't seem to be there anymore(I know 6 years ago right). Only quicksort2d is available and even it appears to be an older version from 2006.

Comment 7 by leeahoward posted on 9/28/2015 at 5:41 PM

Much thanks to the waybackmachine. . https://web.archive.org/web...

Comment 8 by 10basetom posted on 10/16/2015 at 7:53 AM

The UDF at http://www.cflib.org/udf/Qu... appears to be different from the one used in this article. It's now called quickSort2D() instead of quickSort(). The required parameters are also different: arrayToSort, key, down, top