Quicksort (Oz)

From LiteratePrograms

(Redirected from Quicksort (Oz, lists))
Jump to: navigation, search
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

We describe several different Oz implementations of the quicksort algorithm. All of these implementations operate on lists. Therefore, they avoid use of the randomized pivot techniques found in, for example, the C implementation of quicksort, since access to a random element of a list takes O(n) time.


Contents

Implementation

Using lists

The Qsort1 function provides a direct implementation of a list quicksort. It takes as arguments a list to be sorted, and an ordering predicate. Sorting proceeds by case analysis:

  • The empty list (nil) is already sorted, so is simply returned;
  • A single element list is already sorted, so is simply returned;
  • Lists containing more than one element are partitioned into two sublists, which are recursively sorted and then combined to form a sorted list. 
<<Qsort1>>=
fun {Qsort1 Xs P}
   case Xs
   of nil then nil
   [] [X] then [X]
   [] X|Xr then
      L G
   in
      partition and sort
   end
end

The partitioning of a list of length > 1 is done relative to the head of the list, X. We construct an anonymous function that applies the ordering predicate, P, to X and another element of the list. Applying this anonymous function using the library procedure List.partition produces two sublists, L and G, which respectively consist of the list elements less than and greater than (as judged by the ordering predicate) the value of X. Each of these sublists is then recursively sorted, and the results concatenated together such the element X is sandwiched between a sorted list of elements less than it, and a sorted list of elements greater than it. 

<<partition and sort>>=
{List.partition Xr fun {$ Y} {P Y X} end L G}
{List.append {Qsort1 L P} X|{Qsort1 G P}}

Using difference lists

A difference list is a way of representing a single list in terms of the difference between a pair of lists. The list represented by a difference list consists of whatever portion of the first list in the pair is a prefix of the entire second list. For example, the difference list 

[1 2 3 4 5]#[4 5]

represents the list [1 2 3] (since prefixing [1 2 3] onto the second list in the pair yields the first list), while the difference list 

[1 2 3 4 5]#[1 2 3 4 5]

is equivalent to the empty list, since there is no difference between the first and second lists.

This may seem like a rather silly way to store lists. However, it can become a very useful technique when combined when Oz's capability to manipulate unbound variables. For example, given the difference lists 

L1 = (1|2|3|X)#X
L2 = (4|5|Y)#Y

where X and Y are unbound, the two lists can be concatenated in constant time by binding X to the first part of L2 and building a new difference list from the first part of L1 and the second part of L2: 

L3 = (1|2|3|X)#Y
X = (4|5|Y)

This concatentation is significantly faster than the usual O(n) list concatentation operation. Faster concatentations make difference lists an attractive option for algorithms that involve concatenating a lot of lists, such as quicksort.

The difference list implementation of quicksort has essentially the same structure as the regular list quicksort:

  • The empty list (nil) is already sorted, so return an empty difference list (Y#Y);
  • A single element list is already sorted, so return the corresponding single element difference list ((X|Y)#Y);
  • Lists containing more than one element are partitioned into two sublists, which are recursively sorted and then combined (using a constant time difference list concatenation) to form a sorted list. 
<<difference list qsort>>=
proc {Qsort X ?R}
   case X
   of nil then Y in R = Y#Y
   [] [X] then Y in R = (X|Y)#Y
   [] X|Xr then
      L G L1 L2 G1 G2
   in
      {List.partition Xr fun {$ Y} {P Y X} end L G}
      {Qsort L L1#L2}
      {Qsort G G1#G2}
      L2 = (X|G1)
      R = L1#G2
   end
end

We wrap the difference list implementation in a function that hides the use of difference lists, and simply returns a normal list. 

<<Qsort2>>=
fun {Qsort2 Xs P}
   difference list qsort
   Ys
in
   {Qsort Xs Ys#nil}
   Ys
end

Using an accumulator

An alternative way to implement quicksort without using expensive list concatenations is to use an accumulator to store intermediate results. This approach is effectively equivalent to the difference list approach. In fact, the accumulator implementation can be readily derived from the difference list implementation (which is in turn easily derivable from the regular list-based implementation). The steps for performing this derivation are

  1. Change the difference list implementation such that it represents each difference list as two separate lists, instead of a pair of lists. For example, proc {Qsort X ?R} would become proc {Qsort X ?R A}, where R is the now the first part of the difference list and A is the second part.
  2. Note that only the first part of the difference list, R, is actually returned. Make use of this fact to convert proc's into fun's.

The resulting implementation is a standard accumulator-based quicksort. 

<<Qsort3>>=
fun {Qsort3 Xs P}
   fun {Qsort X A}
      case X
      of nil then A
      [] [X] then X|A
      [] X|Xr then
         L G
      in
         {List.partition Xr fun {$ Y} {P Y X} end L G}
         {Qsort L X|{Qsort G A}}
      end
   end
in
   {Qsort Xs nil}
end

Packaging

We package the three quicksort implementations in a functor, which is an Oz module. All three of the functions are exported, making them available to other modules that import the QuicksortList functor. 

<<QuicksortList.oz>>=
functor
export
   Qsort1
   Qsort2
   Qsort3
define
   Qsort1
   Qsort2
   Qsort3     
end

Testing

We provide a simple test harness for the quicksort implementations. The heart of this test harness is the TestSort procedure. This procedure accepts a sorting function, a testname, a stimulus, and an expected response as parameters. It applies the sorting function to the stimulus using the <= ordering function, and checks to see whether the actual result matches the expected one. The results of the test are then printed to the console. 

<<TestSort>>=
proc {TestSort F Testname S R}
   Result
in
   if
      R == {F S Value.'=<'}
   then
      Result = "passed"
   else 
      Result =  "failed"
   end
   {System.showInfo
    {System.printName F} # " - " # Result # " - " # Testname # "."}
end

The test cases provided as part of the test harness are fairly straightforward. One of the tests checks that the sorting function operates correctly on lists of numbers. The other checks that lists of strings are correctly sorted. 

<<test cases>>=
proc {TestNumericSort F}
   Stimulus = [3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3]
   Response = [1 1 2 3 3 3 4 5 5 5 6 7 8 9 9 9]
in
   {TestSort F "numeric sort" Stimulus Response}
end
proc {TestStringSort F}
   Stimulus = ['bob' 'alice' 'barry' 'zoe' 'charlotte' 'fred' 'marvin']
   Response = ['alice' 'barry' 'bob' 'charlotte' 'fred' 'marvin' 'zoe']
in
   {TestSort F "string sort" Stimulus Response}
end

The complete test harness loads the necessary support modules, and then applies the two test procedures to each of the quicksort implementations. Note that imported functions are invoked using names that have a lower case first letter (and a prefixed module name), despite the fact that they are defined with an upper case letter at the start of their names. 

<<quicksort-tests.oz>>=
functor
import
   Application
   System
   Q at 'QuicksortList.ozf' 
define
   TestSort
   test cases
in     
   {System.showInfo "Testing QuicksortList...\n"}
   {TestNumericSort Q.qsort1}
   {TestStringSort Q.qsort1}
   {TestNumericSort Q.qsort2}
   {TestStringSort Q.qsort2}
   {TestNumericSort Q.qsort3}
   {TestStringSort Q.qsort3}
   {Application.exit 0}
end

Building and running

If you have installed the Mozart Programming System, then the quicksort implementations and test harness can be compiled at the command line by issuing the following commands: 

ozc -c QuicksortList.oz
ozc -x quicksort-tests.oz

Running quicksort-tests should produce the following output: 

Testing QuicksortList...
Qsort1 - passed - numeric sort.
Qsort1 - passed - string sort.
Qsort2 - passed - numeric sort.
Qsort2 - passed - string sort.
Qsort3 - passed - numeric sort.
Qsort3 - passed - string sort.
Download code
Retrieved from "http://literateprograms.org/Quicksort_%28Oz%29"
Views