Pretty Quick Sort With C# 3.0

January 29, 2009

tags:
6 comments

Jafar Husain writes about the prettiness of F#’s type inference, but what I really liked in his post was his C# 3.0 implementation for Quick Sort:

1 public static IEnumerable<T> QuickSort<T>(this IEnumerable<T> list) 2 where T : IComparable 3 { 4 if (!list.Any()) 5 { 6 return Enumerable.Empty<T>(); 7 } 8 var pivot = list.First(); 9 var smaller = list.Where(item => item.CompareTo(pivot) <= 0).QuickSort(); 10 var larger = list.Where(item => item.CompareTo(pivot) > 0).QuickSort(); 11 12 return smaller.Concat(new[]{pivot}).Concat(larger); 13 }

Yes, the F# implementation is more concise, but Jafar really reminded how concise can C# be as well. When I first heard about C# 3.0’s var keyword, I belonged to the group that worried about code getting unreadable. Now I’ve grown to realize that type information can be over-rated. Sometimes it is just irrelevant noise.

Add comment
facebook linkedin twitter email

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

6 comments

  1. JApril 7, 2009 ב 3:01

    Yeah, let’s not pull in a two-liner Python of Haskell version, though… Hehe.

    Reply
  2. BillyApril 7, 2009 ב 5:40

    It should be noted that this is not (really) quicksort.

    See http://augustss.blogspot.com/2007/08/quicksort-in-haskell-quicksort-is.html

    Reply
  3. ian rossApril 8, 2009 ב 19:47

    ps. he updated the code to prevent an infinite recursion..

    Reply
  4. ManitraJune 23, 2009 ב 17:08

    Hi,

    This is just awesome !

    I love concise code with just enough recursion to make things done !

    Grats.

    Reply
  5. ногиOctober 14, 2009 ב 1:12

    Слабо моё имя расшифровать 5f7ce4443ca3a1ac3e669bda9276122e ?

    Reply
  6. kittNovember 19, 2009 ב 5:18

    >>”Yeah, let’s not pull in a two-liner Python of Haskell version, though… Hehe.”

    nothing stop anyone to rewrite this into one string:

    public static IEnumerable shortQuickSort(this IEnumerable list) where T : IComparable
    {
    return !list.Any()?Enumerable.Empty
    ():list.Skip(1).Where(item => item.CompareTo(list.First()) < = 0).qSort().Concat(new[] { list.First() }).Concat(list.Skip(1).Where(item => item.CompareTo(list.First()) > 0).qSort());
    }

    Reply