CustomQuickSort ( values ; valueFunction ; direction )

QuickSort using custom evaluation

Average rating: 3.5 (2 votes) Log in to vote

Richard Dyce - Show more from this author
Dyce & Sons Ltd.
http://dyce.com

Sample input:

CustomQuickSort ( "3,5¶4,2¶1,3¶4,1¶1,7¶2,0¶1,9" ; "Middle( \"[t]\" ; Position( \"[t]\" ; \",\" ; -1 ; 1 ) + Length( \",\" ) ; 64000 )" ; True )

Sample output:

"2,0¶4,1¶4,2¶1,3¶3,5¶1,7¶1,9"

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

/*
CustomQuickSort ( values ; valueFunction ; direction )
Sorts values with the popular and reasonably efficient quicksort algorithm

direction is boolean, True for ascending
valueFunction is an evaulatable string, where "[t]" will be replaced with the value, before evaluation occurs,
e.g.

 "Middle( \"[t]\"  ; Position( \"[t]\" ; \" - \"  ; -1 ; 1 ) + Length( \" - \" ) ; 64000 )"

It requires the CustomValuesLessThanOrEqual ( values ; reference ; valueFunction ) and CustomValuesGreaterThan ( values ; reference ; valueFunction ) functions

*/

Let(
	[
		listLength = ValueCount( values );
		pivotIndex = Ceiling( Random * listLength );
		pivot = MiddleValues( values; pivotIndex; 1 );
		pivotValue = Evaluate ( Substitute( valueFunction ; "[t]" ; pivot ) );
		valuesLessPivot = LeftValues( values; pivotIndex -1 ) & RightValues( values; listLength - pivotIndex )
	];

	Case(

		// if values is trivial [only one element]...
		listLength < 2;
		// return values as-is
		values;
		
		// if values is worth sorting...
		// direction evaluates as True then ascending...
		direction ;
		CustomQuickSort( CustomValuesLessThanOrEqual( valuesLessPivot; pivotValue ; valueFunction ) ; valueFunction ; direction ) &  // sort everything less than or equal to pivot
		pivot  &  // place pivot in middle
		CustomQuickSort( CustomValuesGreaterThan( valuesLessPivot; pivotValue ; valueFunction )  ; valueFunction ; direction ); // sort everything greater than pivot
		
		// direction evaluates as False then descending...
		CustomQuickSort( CustomValuesGreaterThan( valuesLessPivot; pivotValue ; valueFunction )  ; valueFunction ; direction ) & // sort everything greater than pivot
		pivot  &  // place pivot in middle
		CustomQuickSort( CustomValuesLessThanOrEqual( valuesLessPivot; pivotValue ; valueFunction ) ; valueFunction ; direction )  // sort everything less than or equal to pivot
		
	)  // end Case()
)  // end Let()

This is an extension of the existing QuickSort( list ) function from Jeremy Bante ( OshVay Systems, Inc. http://www.oshvay.com).

It allows you to effectively use a comparison function so that you can sort more complex values. For example, given a list of coordinates:

"3,5¶4,2¶1,3¶4,1¶1,7¶2,0¶1,9"

You can sort them by their y coordinate:

CustomQuickSort ( "3,5¶4,2¶1,3¶4,1¶1,7¶2,0¶1,9" ; "GetAsNumber( Middle( \"[t]\" ; Position( \"[t]\" ; \",\" ; -1 ; 1 ) + Length( \",\" ) ; 64000 ) )" ; True )

gives:

"2,0¶4,1¶4,2¶1,3¶3,5¶1,7¶1,9"

Comments

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

CustomQuickSort ( values ; valueFunction ; direction )

Comments

Support this website.

Support this website.