QUICK SORT

Quick sort is divide and conquer algorithm .Its one of the most influential algorithm of 20th century.

Its a top down approach every time a element  is taken and is fixed to some position and then from that fixed place array is portioned in two sub arrays(fixing the position of the pivot is termed as portioning the data) which a recursively portioned further.
It is in place sorting algorithm or in situ

Generally we make first element as the pivot in an array but this in all ready  sorted array does n^2 number of steps thus we prefer to do random shuffling to an array before passing it to quick sort function

Explanation-Here we have taken first element of  the array as the pivot we can take any element as the pivot or median for the best performance.If an array was sorted then we would have taken first element as pivot it would have resulted in worst performance.Thus while doing qsort we must put the given array to a shuffling function

Here split function helps in implementing the divide and conquer stuff by dividing the array into sub-arrays and qsort fixes the position of pivot

Time complexity

Best Case  nlogn (in best case number of compares are 1.39nlog(n))

Average Case   nlogn  (Depth of recursion is logarthmic)  

Worst Case n^2

Space Complexity O(n)

Stability* -In normal and efficient implementation of Quick sorting it is not  stable

Shuffling is needed for performance grantee

Optimizing  quick sort

• Use of extra array may help in partitioning but its not worth using it because it takes extra memory(and becomes same as merge sorting)
• it can be improved by using cut off ie after dividing array into small sub arrays and applying insertion sort, insertion sort handles the nearly sorted array efficiently and moreover it can sort the numbers during runtime
•  we can make pivot=median of the data and for large data we can get the median by taking sample the data

Comparison

In average case merge sorting do 39% more compares than quick sorting but quick sorting is faster than merge sorting because it has less data movement

Insertion and merge sort are stable while bubble selection and quick(in an efficient implimentation) are not stable

Insertion and merge sort are stable because in their algorithm we never make equal item pass or swap

What are stable sorting algorithms-:

In a stable sorting algorithms  relative order of the equal elements are maintained because we never swap the elements having the equal values(use full when we have lot many fields and need to arrange the data according to any field as required)


int split(int *a,int lower,int upper)
{   int temp;
    int p=lower+1;
    int q=upper;
    int pivot=a[lower];
    while(q>=p)//>= is must because if only > is used here then there would one less swapping and that will affect the sorting    {
 while(a[p]<pivot)
    p++;
              while(a[q]>pivot)
              q--;
              if(q>p)
              {
               temp=a[p];
              a[p]=a[q];
              a[q]=temp;
                     }           
              }
              temp=a[lower];
              a[lower]=a[q];
              a[q]=temp;
              return q;
}
void qsort(int *a,int lower,int upper)
{
     int i;
     if(upper>lower)
     {
     i=split(a,lower,upper);
     qsort(a,lower,i-1);
     qsort(a,i+1,upper);
     }              
 }
  main()
 {
     int a[10]={11,2,9,13,57,25,17,1,90,3};
     qsort(a,0,9);
     for(int i=0;i<=9;i++)
     cout<<a[i]<<endl;
     getch();
    
 }