Urban Hafner

CTM: Exercise 3-15

Posted by Urban Hafner Mon, 26 Sep 2005 15:34:17 GMT

The problem

Quicksort. The following is a possible algorithm for sorting lists. Its inventor C.A.R. Hoare, called it quicksort, because it was the fastest known general-purpose sorting algorithm at the time it was invented. It uses a divide and conquer strategy to give an average time complexity of O(n_ log _n). Here is an informal description of the algorithm for the declarative model. Given an input list L, then do the following operations:

1. Pick L’s first element, X, to use as a pivot.
2. Partition L into two lists, L1 and L2, such that all elements in L1 are less than X and all elements in L2 are greater than or equal to X.
3. Use quicksort to sort L1 giving S1 and to sort L2 giving S2.
4. Append the lists S1 and S2 to get the answer.

Write this program with difference lists to avoid the linear cost of append.

My solution

I must admit that I didn’t really understand difference lists and what I did here is mostly based on modifying a version of QuickSort with appends into a version with difference lists. But what I did is mostly a copy the idea from the Flatten example in section 3.4.4 and is not based on a deep understanding of difference lists. Anyway, here it is:

fun {QuickSort L}
   fun {Partition Li E Acc1 Acc2}
      case Li
      of nil then
     Acc1#(Acc2)
      [] Li1|Lir then
     if Li1 < E then
        {Partition Lir E Li1|Acc1 Acc2}
     else
        {Partition Lir E Acc1 Li1|Acc2}
     end
      end
   end
   proc {QuickSortD L ?Ds}
      case L
      of nil then Y in Ds=Y#Y
      [] E1|E2|nil then Y in
     if E1 < E2 then
        Ds=(E1|E2|Y)#Y
     else
        Ds=(E2|E1|Y)#Y
     end
      [] E|nil then Y in Ds=(E|Y)#Y
      [] X|_ then L1 L2 Y1 Y2 Y4 in
     L1#L2={Partition L X nil nil}
     Ds=Y1#Y4
     {QuickSortD L1 Y1#Y2}
     {QuickSortD L2 Y2#Y4}
      end
   end
   Ys
in
   {QuickSortD L Ys#nil} Ys
end