Uncategorized

The Brevity of Functional Languages

QuickSort is a well-known, efficient, sort algorithm. In previous posts I've discussed the runtime and space complexity of this algorithm, but there are some other factors that are rather important: brevity and clarity of code. Let's examine this by looking at the implementation of quicksort in C#, Java, C++ and F#.

Here is my version of quick sort in non-generic Java:

   1:      public static void quickSort(int[] input, int start, int finish)
   2:      {
   3:          if (finish-start < 2)
   4:              return;
   5:          
   6:          //pick a pivot
   7:          int pivotIndex = (finish+start)/2;
   8:          
   9:          //partition about the pivot
  10:          int i=start, j=finish;
  11:          while(i<=j)
  12:          {
  13:              while(input[i] < input[pivotIndex])
  14:                  i++;
  15:              
  16:              while(input[j] > input[pivotIndex])
  17:                  j--;
  18:              
  19:              if(i<=j)
  20:              {
  21:                  int temp = input[i];
  22:                  input[i]=input[j];
  23:                  input[j]=temp;
  24:                  i++;
  25:                  j--;
  26:              }
  27:          }
  28:          
  29:          if (start < i-1)
  30:              quickSort(input, start, i-1);
  31:          
  32:          if (i < finish)
  33:              quickSort(input, i, finish);        
  34:      }

And here it is in a generic C# flavour:

   1:          public static void QuickSort<T>(T[] input)
   2:                      where T : IComparable<T>
   3:          {
   4:              QuickSort(input, 0, input.Length - 1);
   5:          }
   6:   
   7:          public static void QuickSort<T>(T[] input, int start, int finish)
   8:              where T:IComparable<T>
   9:          {
  10:              if (finish - start < 2)
  11:                  return;
  12:   
  13:              //pick a pivot
  14:              int pivotIndex = (finish + start) / 2;
  15:   
  16:              //partition about the pivot
  17:              int i = start, j = finish;
  18:              while (i <= j)
  19:              {
  20:                  while (input[i].CompareTo(input[pivotIndex]) < 0)
  21:                      i++;
  22:   
  23:                  while (input[j].CompareTo(input[pivotIndex]) > 0)
  24:                      j--;
  25:   
  26:                  if (i <= j)
  27:                  {
  28:                      T temp = input[i];
  29:                      input[i] = input[j];
  30:                      input[j] = temp;
  31:                      i++;
  32:                      j--;
  33:                  }
  34:              }
  35:   
  36:              if (start < i - 1)
  37:                  QuickSort(input, start, i - 1);
  38:   
  39:              if (i < finish)
  40:                  QuickSort(input, i, finish);
  41:          }

Here's my C++ code :

   1:  void quickSort(int arr[], int left, int right) {
   2:        int i = left, j = right;
   3:        int tmp;
   4:        int pivot = arr[(left + right) / 2];
   5:   
   6:        /* partition */
   7:        while (i <= j) {
   8:              while (arr[i] < pivot)
   9:                    i++;
  10:              while (arr[j] > pivot)
  11:                    j--;
  12:              if (i <= j) {
  13:                    tmp = arr[i];
  14:                    arr[i] = arr[j];
  15:                    arr[j] = tmp;
  16:                    i++;
  17:                    j--;
  18:              }
  19:        };
  20:   
  21:        /* recursion */
  22:        if (left < j)
  23:              quickSort(arr, left, j);
  24:        if (i < right)
  25:              quickSort(arr, i, right);
  26:  }

Here's some Erlang code to do the same:

qsort([]) -> [];
qsort([Pivot|T]) ->
	qsort([X || X <- T, X =< Pivot])
	++ [Pivot] ++
	qsort([X || X <- T, X > Pivot]).

And finally, here's my F# code, that admittedly does it slightly differently in that it selects the first items as the pivot:

#light
open System
 
let rec quickSort ls =
  match ls with
  | [] -> []
  | p::r -> 
     quickSort [for i in r do if (compare i p) <= 0 then yield i] 
     @ [p] 
     @ quickSort [for i in r do if (compare i p) > 0 then yield i]          
 

I know I've mentioned it before on this site, but despite my deep admiration for C++ , Java and C# - they are all great languages - it's painfully clear that, with their advanced list comprehension syntax, functional languages are great at producing succinct code that is very easy to turn into highly parallelized code! With multi-core servers the norm these days these features of functional languages are extremely attractive.

Uncategorized

Sorting Algorithms in F#

A while ago I reviewed basic sorting algorithms in Java and C#. I've been playing a lot with F# over the past 6 months so I'd thought it would be worthwhile whipping up the same algorithms in F#.

The earlier posts with Java and C# implementations are here:
Sorting Fundamentals: Part 1
Sorting Fundamentals: Part 2

Bubble Sort

Everyone knows this is an inefficient algorithm but none-the-less it has "educational value". In my F# implementation I've defined 2 recursive functions, sink and outer. Both functions accept a list and return a new list. The sink function makes a single pass through the list sinking the largest value to the rightmost/last position in the list using simple pattern matching semantics. In lines 7-8 the cons operator (::) is used to separate the first 2 items in the list from the remainder of the list so a greater than pairwise comparison can be make on the leading pair. Note that lists, and indeed all identifiers not explicitly marked as mutable, are immutable so a new list is created rather than returning the original list. In other words, it is not in-place.

The second function, outer, is logically equivalent to the outer loop in the C#/Java implementation that you've no doubt seen before. We pass a list and the list size to this function. The function sinks one value using the function described above, then calls itself recursively on a new list that is a copy of the original list but has one fewer items - the "sunken" element is removed from the end.

    1 #light

    2 open System

    3 

    4 let rec sink ls =

    5     match ls with

    6     | [] -> []

    7     | x::y::rest when x > y -> y::(sink (x::rest))

    8     | x::rest -> x::(sink rest)

    9 

   10 let rec bubbleSort ls =

   11   let rec outer ls lsSize =

   12     match lsSize with

   13     | 0 -> ls

   14     | x -> outer (sink ls) (x - 1)

   15   outer ls (Seq.length ls)

   16 

   17 let mylist = [3;5;1;2;2;78;9;8;43;5;-6]

   18 let mylistsorted = (bubbleSort mylist)

   19 print_any mylistsorted

   20 Console.ReadLine() |> ignore

Insertion Sort

The insertion sort algorithm works by inserting each item into an already sorted sub-list. In F# I've implemented it using 2 recursive functions, insert and insertionSort. Both functions take a list and return a new list. The insert function takes an item and a list and creates a new list which is a copy of the one passed but it inserts the passed item into the new list. This function is designed to take a sorted list or an empty list - which then becomes a sorted list.

The insertionSort function picks off the first item in the list and inserts it into the already-sorted sublist .

    1 #light

    2 open System

    3 

    4 let rec insert x ls = 

    5     match ls with

    6     | []    -> [x]

    7     | y::rest -> if x <= y then x::y::rest

    8                  else y::(insert x rest)

    9 

   10 let rec insertionSort ls =

   11     match ls with

   12     | []    -> []

   13     | x::rest -> insert x (insertionSort rest)     

   14 

   15 let mylist = [3;5;1;2;2;78;9;8;43;5;-6]

   16 let mylistsorted = (insertionSort mylist)

   17 print_any mylistsorted

   18 Console.ReadLine() |> ignore

QuickSort

The quicksort algorithm is a classic divide-and-conquer algorithm. It selects a pivot from the list then creates 2 sub-lists containing all items less than, and greater than the pivot. The result is a new list which is the concatenation of the less-than list, the pivot, and the greater-than list. And, in order to sort the 2 sub-lists it calls itself recursively.

#light
open System
 
let rec quickSort ls =
  match ls with
  | [] -> []
  | p::r -> 
     quickSort [for i in r do if (compare i p) <= 0 then yield i] 
     @ [p] 
     @ quickSort [for i in r do if (compare i p) > 0 then yield i]          
 
let mylist = [3;5;1;2;2;78;9;8;43;5;-6]
let mylistsorted = (quickSort mylist)
print_any mylistsorted
Console.ReadLine() |> ignore

MergeSort

Of all the sort algorithms, quicksort is perhaps the most amenable to functional programming as it can exploit parallelization. If I had 10 billion records in numerous files over many machines a modified version of mergeSort is what you'd want top use, but that's a topic for another post...

    1 #light

    2 open System

    3 

    4 let rec splitList ls n =

    5     match ls with

    6     | [] -> [],[]

    7     | ls when n=0 -> ([],ls)

    8     | head::tail ->

    9         let l1, l2 = splitList tail (n-1);

   10         head::l1, l2

   11 

   12 let rec mergeLists ls1 ls2 =

   13     match ls1, ls2 with

   14     | [],[] -> []

   15     | [],ls2 -> ls2

   16     | ls1,[] -> ls1

   17     | h1::t1, h2::t2 when h1 <= h2 -> h1 :: mergeLists t1 ls2

   18     | h1::t1, h2::t2 -> h2 :: mergeLists ls1 t2

   19 

   20 let rec mergeSort ls =

   21     match ls with

   22     | [] -> []

   23     | [x] -> [x]

   24     | ls ->

   25         let ls1, ls2 = splitList ls (ls.Length/2)

   26         mergeLists (mergeSort ls1) (mergeSort ls2)

   27 

   28 let mylist = [3;5;1;2;2;78;9;8;43;5;-6]

   29 let mylistsorted = (mergeSort mylist)

   30 print_any mylistsorted

   31 Console.ReadLine() |> ignore

As you can see, F# code is succinct and highly expressive. I liken it to Python in it's terseness without the performance penalty! The beauty of F# is a lightweight syntax where whitespace is used instead of block- and scope-defining curly braces, and the clever use of type inference within a strongly-typed type system, so I needn't get bogged down defining explicit types which makes the code's purpose clearer.

Uncategorized

Sorting Fundamentals: Part 2

In Part 1 of this series I detailed the workings and complexity of the O(n2) sorting algorithms - Bubble, Selection and Insertion - giving implementations in both Java and C#. Let's now look at some of the O(n log2 n) algorithms that perform better.

MergeSort

The mergesort is a divide and conquer algo. It splits the input in half then sorts each half separately before merging the results back together. However when it needs to sort each half, it employs the same technique of splitting and merging. Hence it is a recursive algorithm. It is based on 2 important facts: 1) it's simpler to sort a smaller list than a larger list, and (2) merging 2 sorted lists is not computationally intensive. Here is the non-generic implementation in Java:

   1:      public static void mergeSortInPlace(int[] input, int startIndex, int endIndex)
   2:      {
   3:          if (endIndex - startIndex <= 0)
   4:              return;
   5:          
   6:          // split the input into 2 halves
   7:          int half = (endIndex - startIndex + 1)/2;
   8:          
   9:          mergeSortInPlace(input, startIndex,startIndex + half -1);
  10:          mergeSortInPlace(input, startIndex + half, endIndex);
  11:          mergeInPlace(input, startIndex, startIndex + half, endIndex);
  12:      }
  13:      
  14:      private static void mergeInPlace(int[] input, int startA, int startB, int endB)
  15:      {
  16:          int[] c = new int[endB-startA+1];
  17:          int ap=startA,bp=startB,cp=0;
  18:          while (cp < c.length)
  19:          {
  20:              if (bp > endB || (ap <= (startB-1) && input[ap] < input[bp]))
  21:              {
  22:                  c[cp]=input[ap];
  23:                  ap++;
  24:              }
  25:              else
  26:              {
  27:                  c[cp]=input[bp];
  28:                  bp++;
  29:              }
  30:              cp++;
  31:          }
  32:          
  33:          for(int i=startA; i <= endB; i++)
  34:              input[i] = c[i-startA];
  35:      }

Here's the generic C# implementation:

   1:          public static void MergeSortInPlace<T>(T[] input)
   2:              where T : IComparable<T>
   3:          {
   4:              MergeSortInPlace(input, 0, input.Length-1);
   5:          }
   6:   
   7:          public static void MergeSortInPlace<T>(T[] input, int startIndex, int endIndex)
   8:              where T:IComparable<T>
   9:          {
  10:              if (endIndex - startIndex <= 0)
  11:                  return;
  12:   
  13:              // split the input into 2 halves
  14:              int half = (endIndex - startIndex + 1) / 2;
  15:   
  16:              MergeSortInPlace(input, startIndex, startIndex + half - 1);
  17:              MergeSortInPlace(input, startIndex + half, endIndex);
  18:              MergeInPlace(input, startIndex, startIndex + half, endIndex);
  19:          }
  20:   
  21:          private static void MergeInPlace<T>(T[] input, int startA, int startB, int endB)
  22:              where T:IComparable<T>
  23:          {
  24:              var c = new T[endB - startA + 1];
  25:              int ap = startA, bp = startB, cp = 0;
  26:              while (cp < c.Length)
  27:              {
  28:                  if (bp > endB || (ap <= (startB - 1) && (input[ap].CompareTo(input[bp]) < 0)))
  29:                  {
  30:                      c[cp] = input[ap];
  31:                      ap++;
  32:                  }
  33:                  else
  34:                  {
  35:                      c[cp] = input[bp];
  36:                      bp++;
  37:                  }
  38:                  cp++;
  39:              }
  40:              for (int i = startA; i <= endB; i++)
  41:                  input[i] = c[i - startA];
  42:          }

The merge routine is somewhat complicated by the array bounds checking but in essence all it is doing is comparing the head of 2 sequences and returning the minimum of these until no items are left. When either input list is exhausted, the remainder of the other list is returned.

Run Time Complexity

The best way to understand the run time complexity of the mergesort is to see the problem as a binary tree of sub-problems of reducing size.

Since we are splitting in half at each branch the depth of the tree is log2(n). Because no items have been removed or added to the original array - it's merely been partitioned - the total number of comparisons done at each level of the tree is ~O(n). [In fact it's interesting to note that our sort procedure doesn't do any comparisons - only the merge procedure does comparisons.] Thus it follows that the worst case time complexity is ~O(n.log2n). This is also true for the average case.

For the mathematically minded, an alternate way to derive the run time complexity is to examine the recurrence relationship. This is possible because mergesort is a recursive algorithm. So if we let T(n) represent the time it takes to sort n items, the recipe of mergesort yields the following recurrence:

Note that the final term is n because the complexity of merging two sorted list is proportional to the total number of elements across both lists. Of course, to be a recurrence we must specify a base case. Because it's easy to sort/merge a list of size 1, we know T(1) = 0.

Now we can use the master theorem from Introduction to Algorithms [Cormen et.al] to derive the asymptotic complexity. In the above recurrence, a=2, b=2, f(n) = n, according to the generic formula give by Cormen et al. Since logba =log22=1 and f(n) ~ O(n) this is in fact a type 2 case thus T(n) is bounded by O(n.log2n). Check out page 73-75 of Introduction to Algorithms for full details. It a fairly handy rule to make sense of recurrence relationships.

Space Complexity

There are numerous implementations of the mergesort so one has to be careful when defining the space complexity since it is invariably implementation-specific. The implementations given above in both Java and C# are in-place however, since mergesort is a recursive algorithm we are going to be pushing activation records, or stack frames, onto the stack repeatedly. In fact the growth rate of call stack memory is O(log n) since the number of recursive calls made is proportional to the tree depth. Each of these activation records contains a fixed amount of data, some local variables and a return address, but none the less the total size consumed has a defined growth rate. As well, the merge procedure uses auxiliary memory to do the merge. [Doing an in-place merge on contiguous memory in an array is not easy, but it is in a linked list which is why mergesort works better on lists.] The extra memory required for the merge is, at worst, n hence the total space needed for a merge sort is: 2n + log(n). Since n will dominate log(n) in this function, and we need not worry about coefficients when stating asymptotic upper bounds, we say the space complexity ~ O(n).

Uses and Optimisations

Because it employs a divide-and-conquer approach, mergesort is an excellent algorithm to use in situations where the input cannot fit into main memory but must be stored in blocks on disk. Knuth, in the new edition of The Art of Computer Programming, Vol. 3: Sorting and Searching, identified a technique - which he called "randomized striping" - as the method of choice for sorting with parallel disks/reads. This is an slightly modified version of mergesort optimised for use when the data to be sorted is to be read from multiple disks.

If you have multiple cores to play with, the merge sort algorithm can be further optimised since the conventional algorithm has poor performance due to the successive reduction of the number of participating processors by half, and down to one in the last merging stage. An optimised parallel merge sort would utilize all processors throughout the computation to achieve a speedup of (P-1)/log P where P is the number of processors.

Quick-Sort

Quicksort is another very popular divide-and-conquer sorting algorithm. It works be selecting a pivot item, shuffling "lesser" items to positions below the pivot, and "higher" items to positions above the pivot. Leaving the pivot in place, it then recursively does the same procedure to the "lesser" and "greater" sub-lists created when the input was partitioned about the pivot.

Here is my version of quick sort in non-generic Java:

   1:      public static void quickSort(int[] input, int start, int finish)
   2:      {
   3:          if (finish-start < 1)
   4:              return;
   5:          
   6:          //pick a pivot
   7:          int pivotIndex = (finish+start)/2;
   8:          
   9:          //partition about the pivot
  10:          int i=start, j=finish;
  11:          while(i<=j)
  12:          {
  13:              while(input[i] < input[pivotIndex])
  14:                  i++;
  15:              
  16:              while(input[j] > input[pivotIndex])
  17:                  j--;
  18:              
  19:              if(i<=j)
  20:              {
  21:                  int temp = input[i];
  22:                  input[i]=input[j];
  23:                  input[j]=temp;
  24:                  i++;
  25:                  j--;
  26:              }
  27:          }
  28:          
  29:          if (start < i-1)
  30:              quickSort(input, start, i-1);
  31:          
  32:          if (i < finish)
  33:              quickSort(input, i, finish);        
  34:      }

And here it is in a generic C# flavour:

   1:          public static void QuickSort<T>(T[] input)
   2:                      where T : IComparable<T>
   3:          {
   4:              QuickSort(input, 0, input.Length - 1);
   5:          }
   6:   
   7:          public static void QuickSort<T>(T[] input, int start, int finish)
   8:              where T:IComparable<T>
   9:          {
  10:              if (finish - start < 1)
  11:                  return;
  12:   
  13:              //pick a pivot
  14:              int pivotIndex = (finish + start) / 2;
  15:   
  16:              //partition about the pivot
  17:              int i = start, j = finish;
  18:              while (i <= j)
  19:              {
  20:                  while (input[i].CompareTo(input[pivotIndex]) < 0)
  21:                      i++;
  22:   
  23:                  while (input[j].CompareTo(input[pivotIndex]) > 0)
  24:                      j--;
  25:   
  26:                  if (i <= j)
  27:                  {
  28:                      T temp = input[i];
  29:                      input[i] = input[j];
  30:                      input[j] = temp;
  31:                      i++;
  32:                      j--;
  33:                  }
  34:              }
  35:   
  36:              if (start < i - 1)
  37:                  QuickSort(input, start, i - 1);
  38:   
  39:              if (i < finish)
  40:                  QuickSort(input, i, finish);
  41:          }

Run Time Complexity

Like the mergesort, quicksort has 2 components: partitioning about a pivot, and recursion. The first of these, partitioning, is clearly a O(n) operation for a set of size n since we need to scan through all items and perform (n-1) comparisons. If this partition splits the set of items upon which it operates in half each and every time then there will be log2(n) recursive calls, leading to a run time complexity of O(n.log2 n). This is the best case run time complexity for quicksort. However, the partitioning phase might not split the items exactly in half. In the worst case it might select a pivot that has all other (n-1) values above or below it. If such a 1:(n-1) split were to happen on every pass we would have recursion n-levels deep rather than log(n) deep and the total number of comparisons performed would be (n-1) + (n-2) + (n-3)+...+ 1 which, by our knowledge of arithmetic progressions, results in run time complexity of O(n2). That is the worst case run time complexity for quicksort. The chances of this partitioning happening are pretty remote though. Each time a pivot is selected it would have to be the maximum or minimum value in the set of values. Other implementations just pick the first item in the set to be the pivot value, but in this case, if the data is already sorted, you will encounter this repeated 1:(n-1) partitioning and thus worst-case quadratic time complexity.

So we've defined the best-case and the worst-case, what is the average-case I hear you ask. It turns out that the average case run time complexity if also ~O(n.log2 n). To derive this you need to solve the recurrence relationship that considers all possible choices of the pivot selection but rather than detail that here, you can see the details of this analysis on wikipedia, or a more complete description in Section 7.4 of Introduction to Algorithms [Cormen et al].

Space Complexity

As with the mergesort, the space complexity of quicksort is determined by the amount of auxiliary memory needed for interim workings, plus the memory required for the recursive call stack. Again it's implementation specific, but in the implementation above, the partitioning is effectively done in-place so apart from the initial memory required to store the original input, the memory required is purely for the call stack. This implies the space complexity of quicksort is O(log2 n) for the average and best case. In the worst case, as stated earlier, quicksort makes n recursive calls so that would indicate a O(n) space complexity in that case. However, if you were to transform the algorithm from a recursive one to an iterative one the call stack memory component would be considerably reduced. In certain circumstances your compiler will be able to do this automatically for you, assuming you are using a statically-typed language. This is called tail recursion and if it can be done then the worst case space complexity reduces to O(log2 n) from O(n).

To be continued...

UPDATE (Oct 2009):
See these algorithms in F# here.

Next »