Mark
May 25, 2016
8:43 am
Tutorials

Quicksort Algorithm with C# program code

Quick Sort C Programming

In the last post we learnt the merge sort algorithm which is based on divide-and-conquer paradigm. Today we are going to learn one more sorting algorithm which is also follows divide-and-conquer paradigm. In quick sort we use a procedure called ‘Partition()‘ which divides array into two part (not necessarily equal) and then we recursively call the quick sort using C procedure on divided arrays.

The Partition() procedure chooses a pivot element and rearranges the array such that all elements smaller than pivot are put before the pivot and all bigger elements are put at the end. By doing so we have actually found the correct position for pivot element. Partition() procedure returns the index of pivot element after rearranging the array.

So we can describe the quick sort algorithm in three simple steps:

1. Find a pivot element form the array.
2. Rearrange the array so that all the elements smaller than pivot comes before and all the element greater than pivot comes after it. After this step the pivot element is in its final position.
3. Recursively apply step 1 and 2 on the divided array.

Time Complexity: Average Case: O(nlogn) Best Case: O(nlogn) Worst Case: O(n²)
Auxiliary Space: O(1)

C# Program Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ProgramsBlog
{
    class quickSortClass
    {
        // Procedure which return pivot index
        int partition(int[] arr,int start,int end)
        {
            // We assume last element of array as pivot element
            int pivot = end;
            int i = start, j = end,temp;
            while (i < j)
            {
                // traverse the array and find index where element is greater than pivot element
                while (i < end && arr[i] < arr[pivot])
                    i++;
                // traverse the array and find index where element is smaller than pivot element
                while (j > start && arr[j] > arr[pivot])
                    j--;
                
                //exchange elements on indexes found by i and j
                if (i < j)
                {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
            // finally put pivot element at its right position in array
            temp = arr[pivot];
            arr[pivot] = arr[j];
            arr[j] = temp;
            // return pivot index
            return j;
        }
        // Quick sort procedure
        void quicksort(int[] arr, int start, int end)
        {
            if (start < end)
            {
                // find the pivot index
                int pivotIndex = partition(arr,start,end);
                // recursivly call itself for array element before pivot index
                quicksort(arr, start, pivotIndex-1);
                // recursivly call itself for array element after pivot index
                quicksort(arr, pivotIndex + 1, end);
            }
        }
        // Main driver function
        static void Main(string[] args)
        {
            int[] arr = {2,14,12,8,6,9,15,4,5,1,3,11}; // array to be sorted
            quickSortClass qs = new quickSortClass();
            // calling the quicksort procedure
            qs.quicksort(arr, 0, arr.Length - 1);
            // printing the sorted array
            foreach (int x in arr)
            {
                Console.Write(x + " ");
            }
            // pausing console
            Console.ReadKey();
        }
    }
}