QuickSort ( listvalues )

[teka]

Name & Parameters: [color:red][big] QuickSort ( listvalues ) [/big]

Description: This implements the nearly optimal QuickSort algorithm developed by C. Hoare and made well known by Donald Knuth in his tome The Art of Computer Programming. Originally written by Jeremy Bante, I updated it for version 8.5.

It makes me crazy that people are still using the atrocious BubbleSort algorithm!

Sample Input:

Bravo

Delta

Alpha

Charlie

Results:

Alpha

Bravo

Charlie

Delta

Recursive: yes

Formula:

/*

QuickSort ( listvalues )

   Sorts a list with the popular and reasonably efficient QuickSort algorithm

It requires the ValuesLessThanOrEqual ( listvalues ; reference ) and ValuesGreaterThan ( listvalues ; reference ) functions.

Modified by Theo Gantos - TEKA, Inc. - www.tekainc.com

  Changed parameter to listvalues to avoid conflict with new reserved word list

Original Author: Jeremy Bante, OshVay Systems, Inc.

*/



Let (

      [

      listLength = ValueCount( listvalues) ;

      pivotIndex = Ceiling( Random * listLength) ;

      pivot = MiddleValues( listvalues; pivotIndex; 1);

      listLessPivot = LeftValues( listvalues; pivotIndex -1) & RightValues( listvalues; listLength - pivotIndex)

      ] ;

     Case (

              // if list is trivial [only one element]...

              listLength < 2;

              // return list as-is

              listvalues;

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

              )  // endCase

      )  // endLet 

Required Functions: ValuesGreaterThan ( listvalues; reference )

ValuesLessThanOrEqual ( listvalues; reference )

Author(s) teka

Date: 01/28/07

Credits: Jeremy Bante

Disclaimer:

FM Forums does not endorse or warrantee these files are fit for any particular purpose. Do not post or distribute files without written approval from the copyright owner. All files are deemed public domain unless otherwise indictated. Please backup every file that you intend to modify.

[bruceR]

/*

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

It requires the ValuesLessThanOrEqual( list ; reference ) and ValuesGreaterThan( list ; reference ) functions.

MODIFIED by Bruce Robertson to use List function and eliminate trailing returns

*/

Let([

listLength = ValueCount( theList);

pivotIndex = Ceiling( Random * listLength);

pivot = GetValue( theList; pivotIndex);

listLessPivot = LeftValues( theList; pivotIndex -1) & RightValues( theList; listLength - pivotIndex)];

Case(

listLength < 2; GetValue(theList;1);

List(

QuickSort( ValuesLessThanOrEqual( listLessPivot; pivot)) ; pivot ;

QuickSort( ValuesGreaterThan( listLessPivot; pivot))

)

) //end Case()

) //end Let()