Scribd Logo
Upload

Welcome to Scribd!

  • 3 views

    22BPS1201 - Ips-1 Daa

    Uploaded by

    yerrachaitanya1017
    happy birthday and daa ips questions

    Copyright:

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

    22BPS1201 - Ips-1 Daa

    Uploaded by

    yerrachaitanya1017
    3 views6 pages
    happy birthday and daa ips questions

    Original Title

    22BPS1201_IPS-1 DAA

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    happy birthday and daa ips questions

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    3 views6 pages

    22BPS1201 - Ips-1 Daa

    Uploaded by

    yerrachaitanya1017
    happy birthday and daa ips questions

    Copyright:

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

    DAA LAB ASSIGNMENT IPS-1

    NAME: KOUSHIK.Y
    NO:22BPS1201
    2. BUBBLE SORT
    CODE:

    #include <iostream>
    #include<chrono>
    #include<algorithm>
    #include<vector>

    using namespace std;


    int* sort(int arr[], int n){
    for(int i=0;i<n;i++){ // Iterates over each element of the array. This loop runs (n)
    times, where (n) is the size of the array.
    int temp=0;
    for(int j=0;j<n-i-1;j++) // Compares adjacent elements and swaps them if
    necessary. For each iteration (i) of the outer loop, the inner loop runs (n - i - 1)
    times.
    //since here the code snippet compares the values
    if(arr[j]>arr[j+1]){
    it runs for constant time
    temp=arr[j+1]; // swap operation takes place within the
    arr[j+1]=arr[j]; //
    arr[j]=temp; //
    }
    }
    return arr;
    }

    int main()
    {
    int n;
    cout<<"enter the size of array"<<endl;
    cin>>n;
    int arr[n];

    cout<<"enter the elements in the array"<<endl;


    for(int i=0;i<n;i++){
    cin>>arr[i];
    }
    auto start = chrono::high_resolution_clock::now();
    sort(arr,n);

    for(int k=0;k<n;k++){
    cout<<arr[k];
    }
    auto stop = chrono::high_resolution_clock::now();
    cout<<""<<endl;

    auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);


    cout<<"Execution time is:"<<duration.count()<<" milliseconds";

    return 0;
    }

    OUTPUT:
    BEST CASE:
    AVERAGE CASE:

    WORST CASE:
    The provided code implements a bubble sort algorithm
    to sort an array of integers. Let's analyze its time
    complexity in terms of Big O notation, denoted as
    (T(n)), where (n) is the size of the input array.

    Best-case Time Complexity


    In the best case, where the input array is already
    sorted, bubble sort still performs (n - 1) comparisons in
    each pass except the last one, leading to a total of (\
    frac{(n - 1) \times n}{2}) comparisons. Therefore, the
    best-case time complexity is also (O(n^2)).

    The worst-case scenario occurs when the input array is


    sorted in reverse order. In this case, the algorithm
    performs the maximum number of comparisons and
    swaps.
     For the first pass, the inner loop runs (n - 1) times.
     For the second pass, it runs (n - 2) times.
     For the last pass, it runs 1 time.
    The total number of operations in the worst case can
    be represented as the sum of the first (n - 1) natural
    numbers:
    This simplifies to (T(n) = O(n^2)).

    The average-case time complexity is also (O(n^2)). This


    is because, on average, the algorithm performs about
    half the total comparisons and swaps compared to the
    worst case, but since Big O notation describes the
    upper bound, the average case remains (O(n^2)).

    3. Consider an array of A[1, 2, 3, ..., n] be an array of n distinct numbers. If i < j and A[i] >
    A[j], then we call the pair (i, j) as an inversion of A. For example, the five inversions in the
    array A :< 2, 3, 8, 6, 1 > are (1, 5), (2, 5), (3, 4), (3, 5), (4, 5).

    CODE:
    #include <iostream>
    using namespace std;
    int main()
    {
    int n;
    cout<<"enter the size of array"<<endl;
    cin>>n;
    int arr[n];

    cout<<"enter the elements in the array"<<endl;

    for(int i=1;i<=n;i++){ // O(n) - Linear time for iterating through the array
    once
    cin>>arr[i];
    }

    for(int i=1;i<=n;i++){ // O(n^2) - Quadratic time due to nested loop


    structure
    for(int j=1;j<=n;j++){ // O(n) per outer loop iteration - Linear time for
    inner loop
    if(i<j && arr[i]>arr[j]){
    cout<<"("<<i<<","<<j<<")";
    }
    }
    }
    return 0;
    }

    OUTPUT:

    The overall time complexity of the code is dominated by


    the most significant operation, which in this case is the
    nested loop structure checking conditions between pairs
    of array elements. Therefore, the overall time complexity
    of the code is (O(n^2)).

    You might also like