QUICK SORT - ALGORITHM & PROCEDURE

 

Quick Sort is based on Divide & Concur strategy. In which first we try to divide given array into two equal parts , Such that the first element of array move to its sorted location and divide array into two equal parts ,  Such that that first part has smaller elements of array and second part of array has larger element than the first element of array. After performing same quick sort method again and again on these part of array. We get sorted array in just (log base 2 N) passes.

ALGORITHM FOR QUICK SORT:

Algorithm Quick sort ( A , FIRST , LAST )

A is an array with N elements

initially FIRST = 0 and  LAST = N-1

STEP 1   : IF FIRST < LAST

STEP 2   : P = A[ FIRST ]

STEP 3   : Sorting from left hand side and proceeding towards right hand side. Find first element  which is greater than P and set index pointer I to this location.

                    /* 

                        I = FIRST

                        WHILE ( A[I] <= P && I < LAST );  

                          {

                              I = I + 1;

                          } 

                        */

STEP 4    : Now starting from right hand side and proceeding towards left hand side. Find first element which is less than P and set index pointer J to this location.

                    /*

                        J = LAST;

                        WHILE ( A[J] > P && J > FIRST )

                            {

                                J = J-1;

                             }

                        */

STEP 5     : IF ( I < J )

STEP 5.1  : TEMP = A[ I ]

STEP 5.2  : A[ I ] = A[ J ]

STEP 5.3  : A[ J ] = TEMP

STEP 5.4  : END IF

STEP 5.5  : END WHILE

STEP 6     : END IF

STEP 6.1  : TEMP = A[ FIRST ]

STEP 6.2  : A[ FIRST ] = A[ J ]

STEP 6.3  : A[ J ] = TEMP

STEP 7     : END IF

STEP 8     : Recursively Call Quick Sort      

                        CALL QUICK SORT (A , FIRST , J - 1 )

                      {Recursively call quick sort for first part of array }

STEP 9     : Recursively call QUICK SORT ( A, J +1 , LAST )

                 {Recursively call quick sort for second part of array }

STEP 10   : END IF

STEP 11   : END

PROCEDURE FOR QUICK SORT IN C

Copy Code

#include<stdio.h>

#include<conio.h>

#define max 7

int a[20]={9,6,5,2,3,7,4,8};

int main()

{

   int i;

   printf("List before sorting\n");

   

   for(i = 0; i <= max; i++)

      printf("%d ", a[i]);

   quicksort(0, max);

   printf("\nList after sorting\n");

   

   for(i = 0; i <= max; i++)

      printf("%d ", a[i]);

}

void quicksort(int first,int last)

{

 int i,j,temp,p;

 if (first < last)

 {

    p = a[first];

    i = first ;

     /* starting from left hand side */

    j = last ;

     /* starting from right hand side */

    while(i<j)

    {

       while(a[i]<=p && i<last)

       i++;

       while(a[j]>p)

       j--;

       if(i<j)

       {

          temp=a[i];

          a[i]=a[j];

          a[j]=temp;

       }

    }

                   

    temp = a[first];

    a[first] = a[j];

    a[j] = temp;

    quicksort(first,j-1);

    quicksort(j+1,last);

 }

}

Output

List before sorting

9 6 5 2 3 7 4 8

List after sorting

2 3 4 5 6 7 8 9

Evolution of Quick Sort:

1. Best Case of Quick Sort:

Best case for quick sort occur when in each pass first element of array divides given array into two equal parts in each case.

  PASS                    NO. OF ELEMENT SORT                     NO OF ARRAY

    1                                        1                                                   2

    2                                        3                                                   4

    3                                        7                                                   8

    4                                       15                                                                 16

    -                                         -                                                    -

    -                                         -                                                    -

    -                                         -                                                    -

 log₂ N                                                 ( N -1 )                                                               ( N )

    -                                         -                                                     -

    -                                         -                                                     -

    -                                         -                                                     -

( N )                                   ( 2^N -1)                                      ( 2^N ) 

So to sort array of N elements quick sort needs just log₂ N passes. Suppose each pass need at most N comparison , so the total number of comparison will be (N log₂ N) with complexity is O(N log₂ N).

2. Worst Case For Quick Sort:

Worst case for quick sort occur , when given array is already sorted.

For Example : [ 3 ,15 , 18 , 20 , 23 ]

 PASS                    NO. OF ELEMENT SORT                     NO OF ARRAY

    1                                        1                                                     1( N - 1)

    2                                        2                                                     1 ( N - 2)

    -                                         -                                                            -

    -                                         -                                                            -

    -                                         -                                                            -

  ( N -1 )                            ( N -1 )                                                  1 ( 1 )

               

Total Comparison =  1 + 2 + 3 + - - - + (N -1)

                                =  N (N-1)/2

                         F_N = N²/2 -N/2

O F_N = O ( N² )                         , since where O  is big O

Question : Explain why quick sort method is known as unstable method.

Answer  : Quick sort method is known as unstable because their is a big difference between its performance in its best case and in worst case.

Quick sort method behave like a sophisticated sorting algorithm in its best case with complexity [bigO(log₂N)] but in worst case it behave  like sorting algorithm with complexity [O(N²)]. This big difference between time complexity of quick sort make it unstable.