Quicksort (Mathematica)

From LiteratePrograms

Other implementations: AWK | C | C++ | Eiffel | Erlang | Forth | Haskell | Java | JavaScript | Mathematica | Mercury | Oz | Python | Python, arrays | Scala | Sed | Standard ML | Visual Basic .NET | XProc

A functional implementation of the randomized quicksort sorting algorithm in Mathematica is straightforward. Although less efficient in practice than an approach that destructively updates the list, this approach demonstrates the use and conciseness of Mathematica's list processing primitives in a nontrivial context.

Our randomized quicksort will have the following overall structure. We use lists of length 1 as our base condition.

<<quicksort>>=
Quicksort[list_] :=
  Block[{list2,pivot,pivotidx},
        If[Length[list] > 1,
           (extract pivot;
            split, sort, and recombine sublists),
           (* else *) list]];

The algorithm begins by choosing a random value from the list called the pivot and removing it from the list. The Random and Delete functions do the job (keep in mind that list indexing is 1-based in Mathematica):

<<extract pivot>>=
pivotidx = Random[Integer,{1,Length[list]}];
pivot = list[[pivotidx]];
list2 = Delete[list,pivotidx]

Next, we use Select together with anonymous functions to split list into the list of values less than and the list of values greater than or equal to the pivot:

<<list of lesser elements>>=
Select[list2, # < pivot &]
<<list of greater or equal elements>>=
Select[list2, # >= pivot &]

Finally, we recursively sort the sublists and join the results with the pivot in-between:

<<split, sort, and recombine sublists>>=
Join[Quicksort[list of lesser elements],
     List[pivot],
     Quicksort[list of greater or equal elements]]

We can test the function by comparing its result against that of Mathematica's built-in Sort function on a random list:

<<test code>>=
TestQuicksort[max_,length_] :=
  Block[{list},
        (list = Table[Random[Integer,{0,max}], {i,1,length}];
         Quicksort[list] == Sort[list])];
Timing[TestQuicksort[100000, 10000]]

Finally, we wrap this all up in a notebook file for loading into the GUI:

<<quicksort.nb>>=
quicksort
test code

Here's some example output when the code is executed:

{1.852 Second, True}

Download code