Scribd Logo
Upload

Welcome to Scribd!

  • 7 views

    B036-Expt No.2 Aoa

    Uploaded by

    maheshbhosale1212004
    Write a program to implement Merge sort / Binary Search using Divide and Conquer Approach and analyze its complexity.

    Copyright:

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

    B036-Expt No.2 Aoa

    Uploaded by

    maheshbhosale1212004
    7 views12 pages
    Write a program to implement Merge sort / Binary Search using Divide and Conquer Approach and analyze its complexity.

    Original Title

    B036-EXPT NO.2 AOA

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Write a program to implement Merge sort / Binary Search using Divide and Conquer Approach and analyze its complexity.

    Copyright:

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

    B036-Expt No.2 Aoa

    Uploaded by

    maheshbhosale1212004
    Write a program to implement Merge sort / Binary Search using Divide and Conquer Approach and analyze its complexity.

    Copyright:

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

    PART A

    (PART A: TO BE REFFERED BY STUDENTS)

    Experiment No.02
    A.1 Aim:
    Write a program to implement Merge sort / Binary Search using Divide and
    Conquer Approach and analyze its complexity.

    A.2 Prerequisite: -

    A.3 Outcome:
    After successful completion of this experiment students will be able to analyze
    the time complexity of various classic problems.

    A.4 Theory:
    Merge sort is based on the divide-and-conquer paradigm. Its worst-case running
    time has a lower order of growth than insertion sort. Since we are dealing with
    subproblems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p =
    1 and r = n, but these values change as we recurs through subproblems.

    To sort A[p .. r]:

    1. Divide Step

    If a given array A has zero or one element, simply return; it is already sorted.
    Otherwise, split A[p .. r] into two subarrays A[p .. q] and A[q + 1 .. r], each
    containing about half of the elements of A[p .. r]. That is, q is the halfway point
    of A[p .. r].

    2. Conquer Step

    Conquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r].

    3. Combine Step

    Combine the elements back in A[p .. r] by merging the two sorted


    subarrays A[p .. q] and A[q + 1 .. r] into a sorted sequence. To accomplish this
    step, we will define a procedure MERGE (A, p, q, r).
    Algorithm:

    MERGE (A, p, q, r)

    n1 ← q − p + 1
    n2 ← r − q
    Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
    FOR i ← 1 TO n1
    DO L[i] ← A[p + i − 1]
    FOR j ← 1 TO n2
    DO R[j] ← A[q + j ]
    L[n1 + 1] ← ∞
    R[n2 + 1] ← ∞
    i←1
    j←1
    FOR k ← p TO r
    DO IF L[i ] ≤ R[ j]
    THEN A[k] ← L[i]
    i←i+1
    ELSE A[k] ← R[j]
    j←j+1

    Time Complexity:

    In sorting n objects, merge sort has an average and worst-case


    performance of O(n log n). If the running time of merge sort for a list of
    length n is T(n), then the recurrence T(n) = 2T(n/2) + n follows from the definition of
    the algorithm (apply the algorithm to two lists of half the size of the original list and
    add the n steps taken to merge the resulting two lists). The closed form follows
    from the master theorem.
    In the worst case, the number of comparisons merge sort makes is equal to or
    slightly smaller than (n ⌈lg n⌉ - 2⌈lg n⌉ + 1), which is between (n lg n - n + 1) and
    (n lg n + n + O(lg n)).
    Time complexity=O(nlogn)
    PART B
    (PART B: TO BE COMPLETED BY STUDENTS)

    (Students must submit the soft copy as per following segments within two hours of the
    practical. The soft copy must be uploaded on the Blackboard or emailed to the concerned lab
    in charge faculties at the end of the practical in case the there is no Black board access
    available)

    Roll No.: B-36 Name: Mahesh Suresh Bhosale


    Class:SE-B COMPS Batch:B2
    Date of Experiment: Date of Submission
    Grade:

    B.1 Software Code written by student:

    MERGE SORT CODE:

    //MERGE SORT

    #include<stdio.h>

    #include<conio.h>

    int n=0,b[20],c=0;

    void merge(int a[],int l,int mid, int r)

    int i,j,k;

    c++;

    i=l;

    c++;

    j=mid+1;

    c++;

    k=l;
    c++;

    while(i<=mid && j<=r)

    if(a[i]<a[j])

    b[k++]=a[i++];

    c++;

    else

    b[k++]=a[j++];

    c++;

    while(i<=mid)

    b[k++]=a[i++];

    c++;

    while(j<=r)

    b[k++]=a[j++];

    c++;

    for(i=l ,c++; c++,i<=r;i++,c++)

    a[i]=b[i];
    c++;

    void mergesort(int a[],int l,int r)

    int mid;

    c++;

    if(l<r)

    mid=(l+r)/2;

    c++;

    mergesort(a,l,mid);

    c++;

    mergesort(a,mid+1,r);

    c++;

    merge(a,l,mid,r);

    c++;

    void main()

    int i;

    int a[20];

    clrscr();

    printf("Enter the number of elements in array: ");

    scanf("%d",&n);

    printf("\nEnter the elements of the array:");


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

    scanf("%d",&a[i]);

    mergesort(a,0,n-1);

    printf("\nSorted Array: ");

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

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

    printf("\n");

    printf("time complexity of functions are %d\n",c+1);

    getch();

    BINARY SEARCH CODE:

    //BINARY SEARCH

    #include<stdio.h>

    #include<conio.h>

    int binary_search(int A[], int key, int len) {

    int high,low,mid;

    low = 0;

    high = len -1;

    while (low <= high) {

    mid = low + ((high - low) / 2);

    if (A[mid] == key) {
    return mid;

    if (key < A[mid]) {

    high = mid - 1;

    else {

    low = mid + 1;

    return -1;

    int main() {

    int a[10],key,position,size,i;

    clrscr();

    printf("\tBINARY SEARCH\n\n");

    printf("Enter the size of the array:\n");

    scanf("%d",&size);

    printf("Enter the elements of the array:\n");

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

    scanf("%d",&a[i]);

    printf("Enter the element to be searched:\n");

    scanf("%d",&key);

    position = binary_search(a, key, size);

    if (position == -1){

    printf("Not found");

    return 0;

    }
    printf("The position of the element is %d", position+1);

    getch();

    return 0;

    B.2 Input and Output:

    MERGE SORT:
    BINARY SEARCH :
    B.3 Observations and learning:

    Merge sort and binary search are classic algorithms based on the divide
    and conquer approach. Merge sort divides an array into halves, sorts them,
    and merges them, with a time complexity of O(n log n). Binary search
    divides a sorted array in half to efficiently find a target element, with a time
    complexity of O(log n). Learning and implementing these algorithms
    provide insights into recursion, sorting, searching, and algorithmic
    analysis,fostering a deeper understanding of efficient problem-solving
    techniques.

    B.4 Conclusion:

    The experiment successfully implemented Merge Sort and Binary Search


    using the Divide and Conquer approach. Complexity analysis revealed
    efficient performance, with Merge Sort exhibiting O(n log n) time
    complexity and Binary Search O(log n), validating the effectiveness of the
    Divide and Conquer strategy for sorting and searching algorithms.
    B.5 Question of Curiosity
    ************************

    You might also like