Intro

QuickSort is a divide and conquer algorithm. It first divides a large array into two smaller sub-arrays: the low elements and the high elements. QuickSort can then recursively sort the sub-arrays.

The steps are:

  1. Pick an element (the first), called a Pivot, from the array.
  2. Partitioning: Divide the array in two arrays: Smaller and Larger (with elements smaller and strictly larger that the Pivot).
  3. Recursively apply the above steps to Smaller and Larger and join them with the Pivot element in the middle.

The base case of the recursion is arrays of size zero or one, which are in order by definition, so they never need to be sorted. Source: Wikipedia1

Exercise

Write a predicate qs(+List, -Sorted) that returns a sorted variant of List as the difference list Sorted. Use the quick sort algorithm described above to perform the sorting. List partitioning does not need to be in place. The append operation (step 3) must be performed using difference lists.

?- qs([10, 5, 9, 5, 4, 11, 23, 5, 1], S-[]).
S = [1, 4, 5, 5, 5, 9, 10, 11, 23]

?- qs([1337,42,7], S-[an,other,end, 1,2,3]).
S = [7, 42, 1337, an, other, end, 1, 2, 3]