Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    Data Structure Lect13

    Uploaded by

    Hasnain Nisar

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Data Structure Lect13

    Uploaded by

    Hasnain Nisar
    2 views10 pages

    Original Title

    Data Structure lect13

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    2 views10 pages

    Data Structure Lect13

    Uploaded by

    Hasnain Nisar

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 10

    Discrete Structure

    Lecture 13
    Topics

     Merge Sort

     Example of Merge sort

     Algorithm of Merge Sort

     Merging two ordered list

     Algorithm for Fibonacci series


    Merge Sort Steps
    A merge sort begins by splitting the list into individual elements by successively
    splitting lists in two.
    The progression of sublists for this example is represented with the balanced
    binary tree of height 4 shown in the upper half of above Figure.
    Sorting is done by successively merging pairs of lists.
    At the first stage, pairs of individual elements are merged into lists of length
    two in increasing order.
    Then successive merges of pairs of lists are performed until the entire list is put
    into increasing order.
    Merge Sort
    A Recursive Merg Sort

     procedure mergesort (L = a1,...,an)


     if n > 1 then
     m := [ n/2 ]
     L1 := a1, a2,...,am
     L2 := am+1, am+2,...,an
     L := merge ( mergesort (L1), mergesort (L2))
     {L is now sorted into elements in nondecreasing order}
    Merge the two lists L1( 2, 3, 5, 6 ) and
    L2 ( 1, 4 ).
    ALGORITHM: Merging Two List

    procedure merge(L1, L2 : sorted lists)


    L := empty list
    while L1 and L2 are both nonempty
    remove smaller of first elements of L1 and L2 from its list; put it at
    the right end of L
    if this removal makes one list empty then remove all elements from
    the other list and append them to L
    return L{L is the merged list with elements in increasing order}
    Fibonacci Series

    A recursive procedure to find fn , we first express fn as fn−1 + fn−2.

    Then we replace both of these Fibonacci numbers by the sum of two previous Fibonacci
    numbers, and so on.
    When f1 or f0 arises, it is replaced by its value.
    At each stage of the recursion, until f1 or f0 is obtained, the number of Fibonacci numbers
    to be evaluated has doubled.
    Algorithm for Fibonacci Series

    procedure Fibonacci (n: nonnegative integer)

    if n = 0 then return 0
    else if n = 1 then return 1

    else return fibonacci(n − 1) + fibonacci(n − 2)


    {output is fibonacci(n)}
    Evaluating f4 Recursively

    You might also like