[[Property:title|Quicksort]]
[[Property:weight|-7]]
[[Property:uuid|61632685-20ad-293b-44b6-907b15d0447a]]

=Description=

The quicksort example is a concurrent implementation of the well-known [http://en.wikipedia.org/wiki/Quicksort quicksort] sorting algorithm developed by computer scientist [http://en.wikipedia.org/wiki/C._A._R._Hoare C. A. R. Hoare]. Quicksort uses a "divide and conquer" strategy to sort a structure. It applies a basic algorithm to the structure which leads to a division of the elements into to two substructures. Then it applies the same algorithm to each of the substructures, and so on, until the whole structure is sorted. Because of the repetitive application of the same algorithm to evolving parts of the structure, the quicksort is often used in computer science classes to provide students with experience in [http://en.wikipedia.org/wiki/Recursion_(computer_science) recursive] computation. 

In the SCOOP example, instead of recursive calls, substructures are handled (within limits) by separate [[Concurrent programming with SCOOP|SCOOP processors]] running concurrently.


=Highlights=

The quicksort example sorts a randomly generated container of integers. The set-up for this example is done in the root class. It is interactive in the sense that when you run the example, you get to to choose how many elements will be sorted (within certain limits) and you get to provide a seed for the random number generator which will be used to produce the unsorted structure.

The quicksort algorithm is embodied in the class <code>QUICKSORTER</code>, primarily in its routine <code>sort</code>. Instances of <code>QUICKSORTER</code> declared as <code>separate</code> are spawned to sort substructures as the algorithm progresses.

The structures acted upon by <code>QUICKSORTER</code> are managed in instances of class <code>DATA</code>. <code>DATA</code> is a class designed specifically to support the quicksort example. 

When the example runs, separate <code>QUICKSORTER</code> processes are used for the recursive sorts up until a certain depth of recursion is reached. The limit is defined by the <code>NATURAL</code> constant <code>{QUICKSORTER}.max_recursion_depth</code>.