Monday 14 December 2009

C# QuickSort using Continuation Passing Style (As requested by a comment)



using System;
using System.Linq;
using System.Collections.Generic;

public static class ListExtensions
{
    public static Tuple<IEnumerable<T>, IEnumerable<T>> Partition<T>(
         this IEnumerable<T> items, Func<T, bool> p)
    {
        var xs = items.Where(p);
        var ys = items.Except(xs);
        return Tuple.Create(xs, ys);
    }

    public static IEnumerable<T> Loop<T>(
        IEnumerable<T> xs,
        Func<IEnumerable<T>, IEnumerable<T>> cont) where T : IComparable
    {
        if (!xs.GetEnumerator().MoveNext())
            return cont(new T[0]);
        else
        {
            var x = xs.First();
            var xsp = xs.Skip(1);
            var parts = xsp.Partition(y => y.CompareTo(x) > 0);
            return Loop<T>(parts.Item1, lacc =>
                   Loop<T>(parts.Item2, racc =>
                       cont(lacc.Concat(new[] { x }).Concat(racc))));
        }
    }

    public static IEnumerable<T> QuickSort<T>(this IEnumerable<T> xs)
                                 where T : IComparable
    {
        return Loop<T>(xs, x => x);
    }
}

1 comment:

rahul said...

First of all. Thanks very much for your useful post.

I just came across your blog and wanted to drop you a note telling you how impressed I was with the

information you have posted here.

Please let me introduce you some info related to this post and I hope that it is useful for community.

There is a good C# resource site, Have alook

http://CSharpTalk.com

Thanks again
Rahul