# Quicksort (Mathematica)

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