Quicksort Random Integers with PLINQ

The first “homework assignment” of Dr. Erik Meijer’s functional programming course on Channel 9 was to write quicksort using C# (or VB) functional comprehensions.  I did it in a very naïve way, then I wondered if I could get a “free” speed up simply by leveraging some of the Parallel Extensions to .NET 4.0. 

 

My results were mixed.  As the number of integers in the unsorted array increases, the parallel implementation begins to pull away, but with smaller numbers the sequential implementation is faster.  I think I’ll try to do something very similar in Erlang this weekend.  It should be an interesting comparison exercise since Erlang terms are immutable.  A naïve implementation should look pretty similar I think.  Neither of them would be true quicksort implementations, since the algorithm was specified by Hoare to work in a mutable fashion with the original array being changed in situ.

 

My dual core machine yielded times of about 80s and 100s when sorting an array of a thousand for the parallel (QsortP) and sequential (Qsort) methods respectively.  So that’s definitely not impressive, but I did it in a very abstract way.  The same function could sort strings or floats or anything else that implements IComparable. 

Code Snippet

1. using System;
2. using System.Collections.Generic;
3. using System.Linq;
4. using System.Threading.Tasks;
5. using System.Diagnostics;
6.  
7. namespace ConsoleApplication3
8. {
9.     class Program
10.     {
11.         static void Main(string[] args)
12.         {
13.             int[] ints = new int[100];
14.             var rand = new Random();
15.             for (int i = 0; i < ints.Length; i++)
16.                 ints[i] = rand.Next(0, Int32.MaxValue);
17.             int[] sortedP;
18.             int[] sorted;
19.             Time(() => sortedP = QsortP(ints).ToArray());
20.             Time(() => sorted = Qsort(ints).ToArray());
21.             Debugger.Break();
22.         }
23.  
24.         public static IEnumerable<T> QsortP<T>(IEnumerable<T> arr) where T : IComparable
25.         {
26.             if (arr.Count() == 0)
27.                 return arr;
28.             T pivot = arr.First();
29.             var sortLess = new Task<IEnumerable<T>>(() => QsortP(arr.Where(v => v.CompareTo(pivot) < 0)));
30.             var sortMore = new Task<IEnumerable<T>>(() => QsortP(arr.Where(v => v.CompareTo(pivot) > 0)));
31.             sortLess.Start(); sortMore.Start();
32.             var equal = arr.AsParallel().Where(v => v.CompareTo(pivot) == 0);
33.             return sortLess.Result.Concat(equal).Concat(sortMore.Result);
34.         }
35.  
36.         public static IEnumerable<T> Qsort<T>(IEnumerable<T> arr) where T : IComparable
37.         {
38.             if (arr.Count() == 0)
39.                 return arr;
40.             T pivot = arr.First();
41.             return Qsort(arr.Where(v => v.CompareTo(pivot) < 0))
42.                 .Concat(arr.Where(v => v.CompareTo(pivot) == 0))
43.                 .Concat(Qsort(arr.Where(v => v.CompareTo(pivot) > 0)));
44.         }
45.  
46.         public static void Time(Action a)
47.         {
48.             var t = new Stopwatch();
49.             t.Start();
50.             a();
51.             t.Stop();
52.             Debug.Write(t.Elapsed.TotalSeconds);
53.         }
54.     }
55. }