CONCEPT OF QUICK SORT - DATA STRUCTURE

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 greater than P and set index pointer I to this location.

                    /* 

                        I = FIRST

                            DO

                                {

                                    I = I + 1;

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

                        */

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  : ELSE

STEP 5.5  : GOTO STEP 3

STEP 6     : ELSE

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

void quicksort ( int a[ 50 ] , 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 */

            do

                {

                    do

                        {

                                i + + ;

                          }while ( a[ i ] < p    &&    i > last)

                        while ( a[ j ] < p    &&    j > first)

                         {

                                j - - ;

                          }

                if ( i < j )

                {

                     temp = a[ i ];

                     a[ i ] = a[ j ];

                     a[ j ] = temp;

                  }

                 else

                  {

                        break ;

                    }

                    } while ( 1 );

                     temp = a[ first ];

                     a[ first ] = a[ j ];

                     a[ j ] = temp;

                    quicksort ( a , first , j - 1 );

                    quicksort ( a , j + 1 , last );

                    }

                }

NOTE : 

Above program is for sorting in Assending Order. If  we want to sort in dessending order than we only change following:

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

            while ( a[ j ] < p && j > first)

 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 inits best case and in worst case.

                                                              Quick sort method behave like a sophisticated sorting algorithm in its best case with complexity [ big O (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.