Brian Dunning's FileMaker Custom Functions

QuickSort ( list )

QuickSort( list ) sorts list with the popular and reasonably efficient quicksort algorithm

  Average rating: 3.8 (37 votes) Log in to vote

Jeremy Bante   Jeremy Bante
OshVay Systems, Inc.
http://www.oshvay.com

Share on Facebook Share on Twitter

  Sample input:
QuickSort (
"Tye
Mineko
Leia
Giang
Promise
Helen
Leilani
Megan
Alix
Leslie
Heather
Laura
Emilie
Wen-Lian
Marisa
Tricia
Hana
Arianna")
  Sample output:
Alix
Arianna
Emilie
Giang
Hana
Heather
Helen
Laura
Leia
Leilani
Leslie
Marisa
Megan
Mineko
Promise
Tricia
Tye
Wen-Lian

  Function definition: (Copy & paste into FileMaker's Edit Custom Function window)

QuickSort( list ) sorts list with the popular and reasonably efficient quicksort algorithm. It requires the ValuesLessThanOrEqual( list ; reference ) and ValuesGreaterThan( list ; reference ) functions.

FileMaker calculations arenât the best tool for sorting; I wrote this function as an exercise. However, if you are bent on sorting a list of values in a calculation, this function will do it about as well as it can be done in the bounds of a custom function. It will almost always perform better than BubbleSort(); and in the highly-unlikely worst-case senario, still needs only about half as many recursive calls.

To sort list, QuickSort() first extracts a random value from list to act as a âpivot.â list is then separated into a list of values less than or equal to the pivot, and a list of values greater than the pivot. It then recursively sorts these sublists, and concatenates them to produce the final sorted list.

 

Comments

Bill Doerrfeld   Bill Doerrfeld, Seattle
Jun 10, 2009
randomIndex isn't specified, should be pivotIndex right?
 
Bill Doerrfeld   Bill Doerrfeld, Seattle
Oct 19, 2009
Doesn't work properly with duplicate values.
 
Humberto Vargas   Humberto Vargas, Mexico City
Jun 9, 2011
I tried pivotIndex instead of randomIndex and worked.
 
Mike Beargie   Mike Beargie, MainSpring, Inc.
Oct 18, 2016
"list" is a reserved word in the calculation engine, so something like "values" should be used as the parameter instead.
 

Log in to post comments.

 

Note: these functions are not guaranteed or supported by BrianDunning.com. Please contact the individual developer with any questions or problems.

Under construction. Email me your wish list for improvements.