Quicksort Program in C & C++ and Algorithm

Quicksort is a sorting algorithm that uses the divide and conquer strategy . In this method division is dynamically carried out . The Three steps of quicksort are as follows .
1) Divide :Rearrange the elements and split the array into two sub arrays and an element in between .Each element in the left sub array is less than or equal to the middle element and each element in the right sub array is greater than the middle element .
2) Conquer : Recursively sort the two sub arrays .
3) Combine : Combine all the sorted elements in a group to form a list if sorted elements .
Quicksort is a sorting algorithm that also,like merge sort .This algorithm finds the element called pivot , that partitions the array into two halves in such a way that the elements in the left sub array are less then and the elements in the right subarrays are sorted separately .This procedure is recursive in nature with the base criteria,the number of elements in the array are not more than 1. 
         The main task in quick sort is to find the element that partitions the array into two halves and to place it at its proper location in the array .Usually the procedure places the first element in the array at its appropriate location .

Also check : Depth First search Algorithm

         This task is performed as stated below ,
To begin with ,set the index of the first element of the array to 'loc' and 'left' variables and index of the last element of the array to right variable .
Then proceed as follows ,

• Beginning with the element pointed to by right ,the array is scanned from right to left ,comparing each element on the way with the element pointed to by loc , till either ,
• 1) Element smaller than the element pointed to by loc is found .In this case the elements are interchanged and procedure continues with step 2.
• 2) If the value if the right variable becomes equal to the value of loc, the procedure terminates here.This condition indicates that the element is placed at as appropriate position loc .
• Beginning with the element pointed to by left ,the array is scanned from left to right comparing each element on the way with the element pointed to by loc ,till either
• 1) Elements greater than the element pointed to by loc is found .In this case ,the elements are interchanged and procedure continues with step 1.
• 2) If the value of the left variable becomes equal to the value of loc , the procedure terminates here .This condition indicates that the element is placed in its final position loc .

As this procedure terminates ,the first element ,pivot ,of original array will be placed at loc,its appropriate location in the sorted array.The elements to left of it will be less than this element and elements to its right will be greater than this element .

Algorithm for Quick sort : 

partitionarray(a , beg ,end ,loc)

Begin
    Set left=beg, right=end,loc=beg
    Set done=false
    while(!done) do
    while((a[loc]<a[right]) and (loc!=right)) do
        Set right=right-1
        endwhile
        if(loc=right) then
            Set done = true
        else if(a[loc]>a[right]) then
            Interchange a[loc] and a[right]
            Set loc=right
        endif
        if(!done) then
            when (a[loc]>a[left]) and (loc!=left) do
                Set left=left+1
            endwhile
            if(loc=left) then
                Set done=true
            else if(a[loc[<a[left]) then
                Interchange a[loc] and a[left]
                Set loc=left
            endif
        endif
    endwhile
End

Recursive algorithm for Quicksort :
Quicksortrecursive( a , lb , ub)

Begin
    if(lb<ub) then
        Call PartitionArray(a , lb , ub ,loc)
        Call Quicksortrecursive(a , lb , loc-1)
        Call Quicksortrecursive(a , loc+1 ,ub)
    endif
End

Here is a linear array of size n(>1) in memory .This algorithm sorts this array in ascending order using quick sort method .The variable loc is used to hold the index of splitting element .
Also check: Threaded Binary Tree structure and Traversal

Program for Quick sort in C C++ ( Implementing quicksort ) :

#include<iostream>
using namespace std;
template<class T>
class array
{
 private:
  T *a;
  int size;
 public:
  array(int n)
  {
   size=n;
   a=new T[n];
  }
  ~array()
  {
   delete[] a;
  }
  void inputarray();
  void partitionarray(int,int,int &);
  void quicksortrecursive(int,int);
  void quicksort();
  void outputarray();
};
//Function to imput array elements in quicksort 
template<class T>
void array<T>::inputarray()
{
 int i;
 cout<<"\nEnter"<<size<<"element of array\n";
 for(i=0;i<size;i++)
 {
  cin>>a[i];
 }
}
//Function to display array into elements in quicksort
template<class T>
void array<T>::outputarray()
{
 int i;
 for(i=0;i<size;i++)
 {
  cout<<a[i]<<"t";
 }
 cout<<endl;
}
//Function to split array partitions in quicksort
template<class T>
void array<T>::partitionarray(int beg,int end,int & loc)
{
 int left,right,temp;
 boolean done;
 loc=left=beg;
 right=end;
 done=0;
 while(!done)
 {
  while((a[*loc]<=a[right]) && (*loc!=right))
   right--;
   if(*loc==right)
    done=1;
   else if(a[*loc]>a[right])
   {
    temp=a[*loc];
    a[*loc]=a[right];
    a[right]=temp;
    *loc=right;
   }
   if(!done)
   {
    while((a[*loc]>=a[left])&&(*loc!=left))
     left++;
    if(*loc==left)
     done=1;
    else if(a[*loc]<a[left])
    {
     temp=a[*loc];
     a[*loc]=a[left];
     a[left]=temp;
     *loc=left;
    }
   }
  }
 }
 //Recursive function of quicksort program
 template<class T>
 void array<T>::quicksortrecursive(int lb,int ub)
 {
  int loc;
  if(lb<ub)
  {
   partitionarray(lb,ub,loc);
   quicksortrecursive(lb,loc-1);
   quicksortrecursive(loc+1,ub);
  }
 }
 template<class T>
 void array<T>::quicksort()
 {
  quicksortrecursive(0,size-1);
 }
 //Main function
 void main()
 {
  int s;
  cout<<"Enter size of array";
  cin>>s;
  array<int> a(s);
  a.inputarray();
  cout<<"\n Input array is :";
  a.outputarray();
  a.quicksort();
  cout<<"\n Sorted array is :";
  a.outputarray();
 }

Time Complexity of Quicksort :

To find the location of the element that splits the array into two sections is an O(n) operation , because every element in the array is compared to the dividing element .After the division ,each section is examined seperately .If the array is split approximately in half (which is not usually) , then there will be logn splits .
             Therefore , the total comparisons are ,
                   f(n) = nxlogn = O(n logn)
Quick sort is sensitive to the order of the input data .And it gives the worst case performance when the elements are already in the ascending order .Then it divides the array into sections of 1 and (n-1) elements in each call .Thus there will be (n-1) partitions in all.
The efficiency of quicksort is affected by the initial order of elements .
Also check : Binary Tree Traversal Algorithm

Final words !

If I had missed any concept please get it to me through comments . Also you can share your idea , logic through comments .