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
OshVay Systems, Inc.
http://www.oshvay.com

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.*/

Let(
  [
  listLength = ValueCount( list);
  pivotIndex = Ceiling( Random * listLength);
  pivot = MiddleValues( list; pivotIndex; 1);
  listLessPivot = LeftValues( list; randomIndex -1) & RightValues( list; listLength - pivotIndex)
  ];

  Case(

      //if list is trivial [only one element]...
    listLength < 2;
      //return list as-is
    list;

      //if list is worth sorting...
    QuickSort( ValuesLessThanOrEqual( listLessPivot; pivot)) &  //sort everything less than or equal to pivot
    pivot  &  //place pivot in middle
    QuickSort( ValuesGreaterThan( listLessPivot; pivot)) //sort everything greater than pivot

  )  //end Case()
)  //end Let()

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, Seattle Jun 10, 2009
randomIndex isn't specified, should be pivotIndex right?

		Bill Doerrfeld, Seattle Oct 19, 2009
Doesn't work properly with duplicate values.

		Humberto Vargas, Mexico City Jun 9, 2011
I tried pivotIndex instead of randomIndex and worked.

		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.

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

QuickSort ( list )

Comments

Support this website.

Support this website.