CONCEPT OF HEAP SORT - DATA STRUCTURE

For understand Heap Sort we first understand some concept such as:

BINARY TREE : Binary tree is tree which have at most (maximum) two child one is right side and another is left side of element. In binary tree top most element is called Parent / Root node and below of root node is called Child Node. Connecting line is called link. Show in diagram below.👇

HEAP TREE : In heap tree parent data is always greater than child data. Sequencing for placing element in heap tree an order like ( 1,2 ,3,4,5...). show in diagram below 👇

In heap sort first we insert the element in hear tree i.e first we create heap tree by arranging elements and than for sorting we first delete the element from the last inserted element. After that we get list of deleted elements which is in an order or we can say that those elements are sorted automatically.

In short we can say that two step perform for heap sort:

STEP 1: Create Heap Tree

STEP 2: Delete last inserted element from tree.

Now we understand heap tree with the help of an example:

Suppose we want to sort following elements such as:

15 , 25 , 30 , 17 , 80 , 29 , 95

Now we first create heap tree.

CASE 1: Take first element i.e 15 and insert into tree. we get following tree.

Now note single element is always a heap tree.

CASE 2: Take second element i.e 25 and insert it into second position in tree.But we know that in heap tree parent is always greater than child.So before inserting we must check new element 25 to previous element 15 with condition ( P > C) i.e (15 > 25) condition is false so we must perform swapping between them and check " Is the tree is a heap tree ? " , answer is yes so the tree is following.

CASE 3: Take third element i.e 30 and insert it into third position in tree.But we know that in heap tree parent is always greater than child.So before inserting we must check new element 30 to parent element i.e 25 with condition ( P > C) i.e (25 > 30) condition is false so we must perform swapping between them and check " Is the tree is a heap tree ? " , answer is yes so the tree is following.

CASE 4: Take forth element i.e 17 and insert it into forth position in tree.But we know that in heap tree parent is always greater than child.So before inserting we must check new element 17 to parent element i.e 15 with condition ( P > C) i.e (15 > 17) condition is false so we must perform swapping between them and check " Is the tree is a heap tree ? " , answer is yes so the tree is following.

CASE 5: Take fifth element i.e 80 and insert it into fifth position in tree.But we know that in heap tree parent is always greater than child.So before inserting we must check new element 80 to parent element i.e 17 with condition ( P > C) i.e (17 > 80) condition is false so we must perform swapping between them and Now we place 80 in second position and again check whether it is a heap tree or not , we see it violet heap tree condition because their is again need to check second position and first position element i.e 80 and 30 , check  ( P > C) i.e (30 > 80) condition is false so again we perform swapping between them and again check " Is the tree is a heap tree ? " , answer is yes so the tree is following.

CASE 6: Take sixth element i.e 29 and insert it into sixth position in tree.But we know that in heap tree parent is always greater than child.So before inserting we must check new element 29 to parent element i.e 25 with condition ( P > C) i.e (25 > 29) condition is false so we must perform swapping between them and again check " Is the tree is a heap tree ? " , answer is yes so the tree is following.

CASE 7: Take seventh element i.e 95 and insert it into seventh position in tree. But we know that in heap tree parent is always greater than child.So before inserting we must check new element 95 to parent element i.e 29 with condition ( P > C) i.e (29 > 95) condition is false so we must perform swapping between them and again check " Is the tree is a heap tree ? " , answer is No and the tree is following.

Again check condition ( P > C) i.e (80 > 95) condition is false so we must perform swapping between them and the tree is following.

Again check " Is the tree is a heap tree ? " , answer is Yes and the tree is following. All the element are inserted and the tree is a final heap tree. 

Now shorting procedure take place in the above 👆 heap tree.

For sorting list start deleting element from last position i.e 7.

CASE 1: In first case we see that 95 is largest element so we first place the 95 in last position i.e 7 by swapping between 29 & 95 we get.

In the above tree 👆 we delete  95 and than it become the first sorted element.The tree will we.

Now again check the above tree 👆 is a heap tree the answer is no, than we first make it heap tree so swapping done between those elements which not satisfy heap tree condition. i.e element 29 in 1-position and element 80 in 3-position. we get following tree.

Note for deletion always swapping between Root element and element of last position.

CASE 2: In second case we see that 80 is largest element so we first place the 80 in last position i.e 7 by swapping between 29 & 95 we get.

In the above tree 👆 we delete  80 and than it become the second sorted element.The tree will we.

Now again check the above tree 👆 is a heap tree the answer is no, than we first make it heap tree so swapping done between those elements which not satisfy heap tree condition. i.e element 25 in 1-position and element 30 in 2-position. we get following tree.

Similarly same procedure is apply with other elements.

Now we collect the deleted elements i.e: 95, 80 , 30 , 29 , 25 , 17 , 15 they are in sorted in descending order.

PROCEDURE OF HEAP SORT IN C

void heapsort ( int a[50], int n)

{

    int temp;

    while (n > 1)

    {

        createheap ( a ,n );        // CALL HEAP CREATE FUNCTION

        temp = a[1];

         a[1] = a[n];

         a[n] = temp;

        n--;

    }

}

void createheap ( int a[50], int n )

{

    int i , c , p , temp ;

    for ( i=2 ; i<=n ; i++ )

    {

        c = i;

        p = c/2;

        while ( c > 1 && a[c] > a[p] )

        {

            temp = a[c];

            a[c] = a[p];

            a[p] = temp;

            c = p;

            p = c/2;

        }

    }

}

ALGORITHM FOR PROCEDURE HEAP SORT (A, N)

A is an array with N- elements.

STEP 1: WHILE N > 1

STEP 2: CALL SUB PROCEDURE CREATEHEAP (A,N)          

STEP 3: TEMP = A[1]

STEP 4: A[1] = A[N]

STEP 5: A[N] = TEMP

STEP 6: N = N-1

STEP 7: END WHILE

STEP 8: END

ALGORITHM FOR SUB PROCEDURE CREATEHEAP (A,N)

A is an array with N elements.

STEP 1: FOR I=2 TO N DO

STEP 2: C=I   [ where C stands for child position ]

STEP 3: P=C/2  [ where P stands for parent position ]

STEP 4: WHILE  C >1 AND A[C] > A[P]

STEP 5: TEMP = A[C]

STEP 6: A[C] = A[P]

STEP 7: A[P] = TEMP

STEP 8: C = P

STEP 9: P = C/2

STEP 10 : END WHILE

STEP 11: NEXT I

STEP 12: END

EVOLUTION OF HEAP SORT

In heap sort to insert Nth key into a heap tree it need at most (log2N) comparisons. So to sort array with N elements heap sort needs ( Nlog2N) comparisons with complexity (Bigo of) O(nlog2n)

Friends I explain all concept and procedure of HEAP SORT. I hope this post is useful for you.We will meet in next post. 👀👍                

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