Quicksort

Description

The quicksort example is a concurrent implementation of the well-known quicksort sorting algorithm developed by computer scientist 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 recursive computation.

In the SCOOP example, instead of recursive calls, substructures are handled (within limits) by separate 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 QUICKSORTER, primarily in its routine sort. Instances of QUICKSORTER declared as separate are spawned to sort substructures as the algorithm progresses.

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

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