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
This entry was posted in C# and tagged , , , , , , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

8 Comments

  1. Posted August 24, 2012 at 3:30 am | Permalink

    I have been browsing online more than 3 hours today,
    yet I never found any interesting article like yours.
    It is pretty worth enough for me. In my view, if all web
    owners and bloggers made good content as you did, the web will be a lot more useful
    than ever before.

  2. atd
    Posted January 13, 2013 at 10:12 am | Permalink

    I am not clear why you did left+right/2 for getting pivot , it looks like you have to do right-left/2. Your algo is working fine but I am not clear on this step can you explain it.

  3. EyeSack
    Posted January 24, 2013 at 3:12 pm | Permalink

    Hi!

    I wuld like to know why after the swaping you used:

    i++;
    j–;

    Allso thank you for a lovely article.
    Regards

    • Posted January 25, 2013 at 11:06 am | Permalink

      Hi,

      It’s for shortening the area to be sorted. The following animation illustrates this perfectly (the red bar represents the pivot):

      http://commons.wikimedia.org/wiki/File:Sorting_quicksort_anim.gif

      i (left side) starts at 0 and j starts at the highest possible index (right side) of the collection. As the collection is sorted, the length is getting decreased. Thus i becomes larger and j becomes smaller.

      Ferhat

  4. Sabina
    Posted August 5, 2013 at 1:24 pm | Permalink

    Ferhat,
    Good code but it doesn’t work with integers, unless you change all IComparable and replace it by int. Why would you use the IComparable in this example anyway? It also works fine with an array of strings or chars if you change IComparable for string or char respectively . I am new to programming, maybe there is some purpose for an interface in this example and I just don’t see it. Anyway, as I said good code in overall, thank you.
    Sabina

3 Trackbacks

  1. By C# Part Two Arrays « Ivailo Kolarov's Blog on February 21, 2013 at 4:38 pm

    [...] algorithm (find it in Wikipedia). 14.Write a program that sorts an array of strings using the quicksort algorithm (find it in Wikipedia). 15.Write a program that finds all prime numbers in the range [...]

  2. [...] Sort in C# – CodeProject Searching and Sorting Algorithms via C# – CodeProject MergeSort in C# Quicksort algorithm in C# در رابطه با سوالات پی اچ پی هیچی نفهمیدم اصلا چی نوشته [...]

  3. By Quicksort Algorithm | Yana's Personal Blog on July 18, 2013 at 10:45 am

    [...] Supreme Solution to QuickSort This entry was posted in Uncategorized on July 8, 2013 by admin_me. [...]

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

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=""> <strike> <strong>

Why ask?