Quicksort in C# and C++


Quicksort is another common sorting algorithm. Its a divide and conquer based algorithm. Quicksort is better to use with bigger collections as the time complexity is better in the long run. For smaller collections its better to use the Bubble Sort or the Insertion Sort.

Algorithm explained:

  1. Pick a pivot value. In Quicksort, the pivot value is used to partition the array; and, in a unsorted array, it can either be the first value of the array, the middle, end, or rather randomly choosing a value within the array can be the pivot. In this tutorial, the median value will be the pivot. In theory, any value can be considered a pivot because any value is as good as the other. However, ideally for good performance measures, it is good practice to obtain a pivot value that is in the middle of the array (it can be obtained by selecting 3 random values, and setting the middle value as the pivot). Choosing a middle value lessens the chance that extreme values such as those that are too high or too low are chosen, and this is more efficient (less work done).
  2. Move anything less than the pivot, left of the pivot value, move anything greater than the pivot, right of the pivot (assuming ascending order)
  3. Recurse on each side (basically, repeat steps 1 & 2 for the left side until the left side is sorted, and do the same for the right side)
  4. Once we run out of comparisons to make, sorting is done

Quick sort has O(nlog n) time complexity, for BEST and AVERAGE case. The reason for this is that it consists of two parts. The first is the partitioning of the array which had a run time of O(n) each time its executed. The QuickSort recursion has a run time of O(log n) due to every time Partition does an operation (as in pivot, split, and sort), the recursion from it creates a binary tree of calls. For the WORST case, Quicksort has O(n²) runtime, this is when the collection is nearly sorted or sorted already.

For this implementation, there is a single method called QuickSort that takes 3 parameters: array[], integer begin, integer end. The partitioning will also be done inside this method. We have a separate swap method that swaps two values in the array.

Sample code in C#

        static void Main(string[] args)
        {
            int[] arr = { 6, 2, 4, 9, 1, 7, 3, 5, 8 };
            quicksort(arr, 0, arr.Length - 1);
            Console.WriteLine();
            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write("{0} ", arr[i]);
            }
            Console.ReadLine();
        }
        static void quicksort(int[] arr, int begin, int end)
        {
             int pivot = arr[(begin + (end - begin) / 2)];
             int left = begin;
             int right = end;
             while (left <= right)
             {
                  while (arr[left] < pivot)
                  {
                      left++;
                  }
                  while (arr[right] > pivot)
                  {
                      right--;
                  }
                  if (left <= right)
                  {
                      swap(arr, left, right);
                      left++;
                      right--;
                  }
              }
              if (begin < right)
              {
                  quicksort(arr, begin, left - 1);
              }
              if (end > left)
              {
                  quicksort(arr, right + 1, end);
              }
        }
        static void swap(int[] items, int x, int y)
        {
            int temp = items[x];
            items[x] = items[y];
            items[y] = temp;
        }

C++:

#include <iostream>
#include <string>
using namespace std;
void quicksort(int items[], int begin, int end);
void swap(int items[], int &x, int &y);
int main()
{
   int items[] = {6, 2, 4, 9, 1, 7, 3, 5, 8};
   int sizeOfArray = (sizeof(items)/sizeof(*items));
   quicksort(items, 0, sizeOfArray - 1);
   for(unsigned int i = 0; i < sizeOfArray; i++)
   {
       cout<<items[i]<<" ";
   }
   cin.get();
}
void quicksort(int items[], int begin, int end)
{
    int pivot = items[(begin+(end-begin)/2)];
    int left = begin;
    int right = end;
    while(left <= right)
    {
        while(items[left] < pivot)
        {
            left++;
        }
        while(items[right] > pivot)
        {
            right--;
        }
        if(left <= right)
        {
            swap(items, left, right);
            left++;
            right++;
        }
    }

    if(begin < right)
    {
        quicksort(items, begin, left - 1);
    }
    if(end > left)
    {
        quicksort(items, right + 1, end);
    }
}
void swap(int items[], int &x, int &y)
{
    int temp = items[x];
    items[x] = items[y];
    items[y] = temp;
}

Further illustrations:

quicksort_21 quicksort_ideal

Interactive demo: http://me.dt.in.th/page/Quicksort/

Advertisements

6 thoughts on “Quicksort in C# and C++

  1. Pingback: Insertion Sort Demo | Bits and Pieces of Code

  2. Pingback: Mergesort | Bits and Pieces of Code

  3. You should state whether the time complexity is worst case, average case, or best case. For example, the average case of quick sort is O(n * log n) but the worst case is O(n^2). Usually, in algorithm analysis it is better to state the worst case run time of the algorithm.

    Like

  4. Pingback: Heapsort C# Tutorial | Bits and Pieces of Code

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s