Quicksort algorithm in C#

Quicksort is a divide and conquer sorting algorithm. This example uses the quicksort algorithm to sort an array of string elements.

How it works

The algorithm starts by choosing a pivot value. It proceeds by partitioning the elements. Elements larger than the pivot are partitioned on the right side of the pivot and element smaller than the pivot are partitioned on the left side of the pivot. It then recursively applies the algorithm on the partitions.

Sorting animation (Source: http://en.wikipedia.org/wiki/Quicksort)

Performance

O(N log N) (linearithmic) and O(N^2) (quadratic) in worst case.

Example in C#

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

namespace Quicksort
{
    class Program
    {
        static void Main(string[] args)
        {
            // Create an unsorted array of string elements
            string[] unsorted = { "z","e","x","c","m","q","a"};

            // Print the unsorted array
            for (int i = 0; i < unsorted.Length; i++)
            {
                Console.Write(unsorted[i] + " ");
            }

            Console.WriteLine();

            // Sort the array
            Quicksort(unsorted, 0, unsorted.Length - 1);

            // Print the sorted array
            for (int i = 0; i < unsorted.Length; i++)
            {
                Console.Write(unsorted[i] + " ");
            }

            Console.WriteLine();

            Console.ReadLine();
        }

        public static void Quicksort(IComparable[] elements, int left, int right)
        {
            int i = left, j = right;
            IComparable pivot = elements[(left + right) / 2];

            while (i <= j)
            {
                while (elements[i].CompareTo(pivot) < 0)
                {
                    i++;
                }

                while (elements[j].CompareTo(pivot) > 0)
                {
                    j--;
                }

                if (i <= j)
                {
                    // Swap
                    IComparable tmp = elements[i];
                    elements[i] = elements[j];
                    elements[j] = tmp;

                    i++;
                    j--;
                }
            }

            // Recursive calls
            if (left < j)
            {
                Quicksort(elements, left, j);
            }

            if (i < right)
            {
                Quicksort(elements, i, right);
            }
        }

    }
}

Output:

z e x c m q a
a c e m q x z