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.

                              

CONCEPT OF INSERTION SORT - DATA STRUCTURE

In insertion sort newly inserted element are placed to their sorted location.

Suppose , if we want to insert 5 elements into required space or place and ( 0 , 1 , 2 , 3 , 4 ) are their index or location where the element are stored. Now we first check the space whether it is require for inserting element or not.If space is required.

                    

Suppose we want to insert first element such as (15) , than we first check space at 0th location , if space is available than (15) is stored in 0th location.

In second time we want to insert (10) , than we check the condition, whether the previous right most element (15) is  greater than (10) or not. If it is true than (15) is swapped in next location that is (1) and (10) is stored in 0th location.

In third time we want to insert (5) than we check the condition whether the previous right most element (15) is greater than (5) or not , if it is true than (15) is swapped in next location i.e (2) and space is required for (5) but before store in location (2) , we again check with the right most element i.e (10) , whether it is greater than (5) or not.If it is true than (10) will be swapped into next location i.e (1) and (5) is stored in 0th location.

     

In this way we insert the further elements such as (13) & (17) from above example.

           

ALGORITHM OF INSERTION SORT:

Algorithm Insertionsort  (A , N)

A is an array with N elements.

STEP 1  : FOR I = 0 TO N - 1 DO

STEP 2  : K = I - 1

STEP 3  : READ X

STEP 4  : WHILE K > = 0  AND  A [K] > X

STEP 5  : A[ K + 1] = A[K]

STEP 6  : K= K + 1

STEP 7  : END WHILE

STEP 8  : A[ K + 1] = X

STEP 9  : NEXT I

STEP 10: END

PROCEDURE OF INSERTION SORT:

void Insertionsort sort ( int a[50] , int n )

{

        int i , k , x ;

        for(  i=0 ; i<=n-1 ; i++ )

        {

                k = i - 1;

                printf ( " Enter x: " ) ;

                scanf ( " % d " , & x ) ;

                while ( k >=0 && a[k] > x)

                {

                    a [ k + 1 ] = a[k] ;

                    k - - ;

                }

                a [ k + 1] = x ;

        }

}

Note , here (k)  point to right most element.

LOGIC DIAGRAM

EVALUATION OF INSERTION SORT:

For evaluation of insertion sort their are two cases :

1. Best Case Complexity for Insertion Sort :

Best case for insertion sort occur when newly inserted element is greater than all array element than (N) element needs only (N-1) comparison one for each (N-1) elements and zero for first elements with complexity beg O of (n).

2. Worst Case  Complexity for Insertion Sort :

Worst case for insertion sort occur when newly inserted element is less than all array elements.

To insert 1st element insertion sort need 0 compassion.  

To insert 1st element insertion sort need 1 compassion.  

To insert 1st element insertion sort need 2 compassion.  

To insert 1st element insertion sort need 3 compassion. 

-                        -

-                        -

-                        -

To insert 1st element insertion sort need (n - 1) compassion.  

--------------------------------------------------------------------------

Total  =  n (n - 1) / 2

--------------------------------------------------------------------------

fn =  n2 / 2  - n / 2  

Ofn =  O(n2)   

CONCEPT OF BUBBLE SORT - DATA STRUCTURE

In Bubble Sort method to sort array of n element first we create (n-1) bubble (Collection of two successive array element).

In first pass first element of each bubble is compared with second element of bubble such that , If first element is greater than second element of bubble both are swapped.

After performing such (n-1) comparison and swaps largest element of array move to last position of array i..e its sorted location. After performing such (n-1) passes we get a sorted array.   

ALGORITHM OF BUBBLE SORT:

ALGORITHM Bubble Sort (A, N)

A IS AN ARRAY WITH N ELEMENT.

STEP 1   : FOR I=1 TO N-1 DO

STEP 2   :  FLAG = 0

STEP 3   :  FOR J =1 TO N-1 DO

STEP 4   :  IF A[ J - 1 ]  > A[ J ]

STEP 4.1:  TEMP = A[ J - 1 ]

STEP 4.2:  A[ J -1 ] = A [ J ]

STEP 4.3:  A[ J ] = TEMP

STEP 4.4:  FLAG = 1

STEP 5   :  END IF

STEP 6   :  NEXT J

STEP 7   :  IF FLAG == 0 THEN GOTO J

STEP 8   :  NEXT I

STEP 9   :  END 

FUNCTION OR PROCEDURE IN C:

Void bubblesort ( int a[50] , int n)

{

    int i, j, flag, temp;

    for ( i=1 ; i <= n-1 ; i++)

    {

        flag = 0;

        for ( j= 1; j<= n-i ; j++)

        {

            if (a[ j-1 ] > a[ j ])

                {

                    temp = a[j -1];

                    a[ j-1] = a[ j ];

                    a[ j ] = temp;

                    Flag = 1;

                }

        }

        if ( Flag == 0)

        break;

    }

}

EXAMPLE:

EXPLANATION :

By the help of above figure we can easily understand the working of Bubble Sort. In above example we take 5 number of element for sorting , so n=5 . These five elements are { 17 , 19 , 3 , 4 , 13 }, these elements are stored in any array a[50] = { 17 , 19 , 3 , 4 , 13 }, a[index] index = 0,1,2,3,4 it represent the position of elements in array. Here all elements are sorted in IV Passes ( I ) represent number of passes. The outer loop is controlled by I and the inner loop is controlled by J. On the basis of I & J values elements are compared. Such as a[0] i.e 17 ,a[1] i.e 19 etc.

Comparison Method : For one outer loop i.e value of I, inner loop will run [<=( n-I )] times. The mechanism of inner loop is controlled by J and terminated by value of I. Here the main mechanism is swapping between number with condition [  if (a[ J-1 ] > a[ J ]) ] .If condition become true then swapping done between numbers of value [ ( J - 1 ) , J ].

For example :

when I = 1 , J=1 , J-1=0

Condition: [  if (a[ J-1 ] > a[ J ]) ] , i.e a[0]>a[1]

a[0] =17 , a[1] = 19

CASE 1: 17 > 19 : Condition=F : No Swapping between 17 & 19 : J=J+1

a[1]=19 , a[2] =3

CASE 2 : 19 > 3 : Condition=T : Swapping take place between 19 & 3 : J=J+1

New shorted List : 17 , 3 , 19 , 4 , 13

a[2]=19 , a[3] =4

CASE 3: 19 > 4 : Condition=T : Swapping take place between 19 & 4 : J=J+1

New shorted List : 17 , 3 , 4 , 19 , 13

a[3]=19 , a[4] =13

CASE 4: 19 > 4 : Condition=T : Swapping take place between 19 & 13 : J=J+1

New shorted List : 17 , 3 , 4 , 13 , 19 ← First Sorted List

CASE 5: Check Condition : J < = N-I , i.e 5< = 4 : False : Terminate Inner Loop : I= I+1

Now I=2 : J=0 : Do same process as above on  Following List :17 , 3 , 4 , 13 , 19

Try your self until not get following list

3 , 4 , 13 , 17 , 19 ← Final Sorted List

Evaluation of Bubble Sort:

There are two cases for evaluating bubble sort:

1. Best Case Complexity For Bubble Sort: 

Best Case for bubble sort occur when given array is already sorted in such case bubble sort need only one pass and ( n - 1 ) comparison with complexity.

            Ofn =  O(n-1)

Now neglect constants

        Ofn =  O(n)

2. Worst Case Complexity  For Bubble Sort: 

In worst case if bubble sort need ( n - 1 ) passes as:

1st  Pass need n-1 comparisons

2nd Pass need n-1 comparisons

3rd Pass need n-1 comparisons

-----                    ----

-----                    ----

( n - 1 ) Pass need  1 comparisons

--------------------------------------------------

Total =  1 + 2 + 3 + ---- ( n - 1 )

--------------------------------------------------

            fn =  n ( n - 1 ) / 2

            fn =  n2 / 2 -  n  / 2

           Ofn =  O(n2)

It shows the time complexity of bubble sort is  n2