Question

In: Computer Science

WRITE USING C++ CODE, TOPIC :Analysis of Algorithms Computer Science. PLEASE DONT FORGET RUNNING TIME In...

WRITE USING C++ CODE, TOPIC :Analysis of Algorithms Computer Science. PLEASE DONT FORGET RUNNING TIME

In this lab, you will implement Heap Sort algorithm for the same inputs.

For each algorithm, and for each n = 100, 200, 300, 400, 500, 1000, 4000, 10000, measure its running time and number of steps when the input is (1) already sort, i.e. n, n-1, …, 3, 2,1; (2) reversely sorted 1, 2, 3, … n; (3) random permutation of 1, 2, …, n; (4) 50 instances of n random numbers generated in the range of [1..n].

Note:

(1) You may have to repeat the algorithm many times, each time you need to initialize the array.

(2) Your running time should exclude the time for initialization.

(3) All measurement should be done in a single run, i.e. you do not need to run once for n=100, another time for n=200, etc

Solutions

Expert Solution

#include <iostream>
#include<bits/stdc++.h>
#include<stdlib.h>
using namespace std;

void heapify(int a[], int n, int i)   //This function takes O(log n) time
{
    int large = i;
    int left = 2*i + 1;
    int right = 2*i + 2;
    // If the left child > root
    if (left < n && a[left] > a[large])
        large = left;
    // If the right child > large so far
    if (right < n && a[right] > a[large])
        large = right;

    // If largest is not the root
    if (large != i)
    {
        swap(a[i], a[large]);
        heapify(a, n, large);
    }
}

void heapSort(int a[], int n)
{
    int i;
    for ( i = n / 2 - 1; i >= 0; i--)    //This takes O(n) time.
        heapify(a, n, i);
    for (i=n-1; i>0; i--)
    {
        swap(a[0], a[i]);
        heapify(a, i, 0);
    }
}

int getNum(vector<int>& v)
{
    int n,index,num;
     n = v.size();
    srand(time(NULL));
    index = rand() % n;
    num = v[index];
    swap(v[index], v[n - 1]);
    v.pop_back();
    return num;
}

// This is the function to generate n non-repeating random numbers
int* generateRandom(int n)
{
    vector<int> v(n);
    int* a = new int[10000];
    int k=0,i;
    for (i = 0; i < n; i++)
        v[i] = i + 1;
    while (v.size()) {
        a[k++]=getNum(v);
    }
    return a;
}

int main()
{
    clock_t time_req;
    int arr[10000],i,n;
    n=100;
    while(n<=500)
    {
        for(i=0;i<n;i++)
        {
            arr[i]=n-i;
        }
        time_req = clock();
        heapSort(arr, n);
        time_req = clock()- time_req;
        cout << "Running time in case of already sorted array of "<<n<<" elements is : "<< (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;
        for(i=0;i<n;i++)
        {
            arr[i]=i+1;
        }
        time_req = clock();
        heapSort(arr, n);
        time_req = clock()- time_req;
        cout << "Running time  in case of reversely sorted array of "<<n<<" elements is : "<< (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;

        int *a=generateRandom(n);
        time_req = clock();
        heapSort(a, n);
        time_req = clock()- time_req;
        cout << "Running time  in case of random permutations of "<<n<<" elements is : "<< (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;

        cout << "Running time in case of 50 instances of a random array of "<<n<<" elements is   :   ";
        for(int j=0;j<50;j++)
        {
            for(i=0;i<n;i++)
            {
                arr[i]=rand()%n+1;
            }
            time_req = clock();
            heapSort(arr, n);
            time_req = clock()- time_req;
            cout <<(float)time_req/CLOCKS_PER_SEC << "     ";
        }
        n+=100;
        cout<<endl<<endl;
    }

    for(i=0;i<1000;i++)
    {
        arr[i]=1000-i;
    }
    time_req = clock();
    heapSort(arr, 1000);
    time_req = clock()- time_req;
    cout << "Running time in case of already sorted array of 1000 elements is : "<< (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;
    for(i=0;i<1000;i++)
    {
        arr[i]=i+1;
    }
    time_req = clock();
    heapSort(arr, 1000);
    time_req = clock()- time_req;
    cout << "Running time  in case of reversely sorted array of 1000 elements is : "<< (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;

    generateRandom(1000);
        time_req = clock();
        heapSort(arr, 1000);
        time_req = clock()- time_req;
        cout << "Running time  in case of random permutations of 1000 elements is : "<< (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;

     cout << "Running time in case of 50 instances of a random array of 1000 elements is   :   ";
    for(int j=0;j<50;j++)
        {
            for(i=0;i<1000;i++)
            {
                arr[i]=rand()%1000+1;
            }
            time_req = clock();
            heapSort(arr, 1000);
            time_req = clock()- time_req;
            cout <<(float)time_req/CLOCKS_PER_SEC << "     ";
        }
    cout<<endl<<endl;
    for(i=0;i<4000;i++)
    {
        arr[i]=4000-i;
    }
    time_req = clock();
    heapSort(arr, 4000);
    time_req = clock()- time_req;
    cout << "Running time in case of already sorted array of 4000 elements is : "<< (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;
    for(i=0;i<4000;i++)
    {
        arr[i]=i+1;
    }
    time_req = clock();
    heapSort(arr, 4000);
    time_req = clock()- time_req;
    cout << "Running time  in case of reversely sorted array of 4000 elements is : "<< (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;

    generateRandom(4000);
        time_req = clock();
        heapSort(arr, 4000);
        time_req = clock()- time_req;
        cout << "Running time  in case of random permutations of 4000 elements is : "<< (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;

    cout << "Running time in case of 50 instances of a random array of 4000 elements is   :   ";
    for(int j=0;j<50;j++)
        {
            for(i=0;i<4000;i++)
            {
                arr[i]=rand()%4000+1;
            }
            time_req = clock();
            heapSort(arr, 4000);
            time_req = clock()- time_req;
            cout <<(float)time_req/CLOCKS_PER_SEC << "     ";
        }

    cout<<endl<<endl;
    for(i=0;i<10000;i++)
    {
        arr[i]=10000-i;
    }
    time_req = clock();
    heapSort(arr, 10000);
    time_req = clock()- time_req;
    cout << "Running time in case of already sorted array of 10000 elements is : "<< (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;
    for(i=0;i<10000;i++)
    {
        arr[i]=i+1;
    }
    time_req = clock();
    heapSort(arr, 10000);
    time_req = clock()- time_req;
    cout << "Running time  in case of reversely sorted array of 10000 elements is : "<< (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;

    generateRandom(10000);
        time_req = clock();
        heapSort(arr, 10000);
        time_req = clock()- time_req;
        cout << "Running time  in case of random permutations of 10000 elements is : "<< (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;

    cout << "Running time in case of 50 instances of a random array of 1000 elements is   :   ";
    for(int j=0;j<50;j++)
        {
            for(i=0;i<10000;i++)
            {
                arr[i]=rand()%10000+1;
            }
            time_req = clock();
            heapSort(arr, 10000);
            time_req = clock()- time_req;
            cout <<(float)time_req/CLOCKS_PER_SEC << "     ";
        }

        cout<<endl<<endl;
    return 0;
}

The ouput of the code is as follows :

PLEASE LIKE THE ANSWER IF YOU FIND IT HELPFUL OR YOU CAN COMMENT IF YOU NEED CLARITY / EXPLANATION ON ANY POINT.


Related Solutions

WRITE USING C++ CODE, TOPIC :Analysis of Algorithms Computer Science. PLEASE DONT FORGET RUNNING TIME In...
WRITE USING C++ CODE, TOPIC :Analysis of Algorithms Computer Science. PLEASE DONT FORGET RUNNING TIME In this lab, you will implement Heap Sort algorithm for the same inputs. For each algorithm, and for each n = 100, 200, 300, 400, 500, 1000, 4000, 10000, measure its running time and number of steps when the input is (1) already sort, i.e. n, n-1, …, 3, 2,1; (2) reversely sorted 1, 2, 3, … n; (3) random permutation of 1, 2, …,...
WRITE USING C++ CODE, TOPIC :Analysis of Algorithms Computer Science. PLEASE DONT FORGET RUNNING TIME In...
WRITE USING C++ CODE, TOPIC :Analysis of Algorithms Computer Science. PLEASE DONT FORGET RUNNING TIME In this lab, you will implement Heap Sort algorithm for the same inputs. For each algorithm, and for each n = 100, 200, 300, 400, 500, 1000, 4000, 10000, measure its running time and number of steps when the input is (1) already sort, i.e. n, n-1, …, 3, 2,1; (2) reversely sorted 1, 2, 3, … n; (3) random permutation of 1, 2, …,...
Code in C++ please You are going to write a program for Computer test which will...
Code in C++ please You are going to write a program for Computer test which will read 10 multiple choice questions from a file, order them randomly and provide the test to the user. When the user done the program must give the user his final score
PLEASE DONT COPY FROM INTERNET PLAGIRISM IS PROHIBITED WRITE 2000 WORDS ON THE TOPIC. TOPIC: INTERNATIONAL...
PLEASE DONT COPY FROM INTERNET PLAGIRISM IS PROHIBITED WRITE 2000 WORDS ON THE TOPIC. TOPIC: INTERNATIONAL TRADE AND DYNAMIC OF UAE (REQUIRE 2000 WORDS) 1. Introduction of the topic 2. Review of literature 3. Data, methodology 4. Analysis & Findings of the study 5. Conclusion 6. Reference
please write the code in C not c++, and not to use Atoi or parseint to...
please write the code in C not c++, and not to use Atoi or parseint to parse the string, Thank you. #include <stdio.h> #include <stdbool.h> /* * The isinteger() function examines the string given as its first * argument, and returns true if and only if the string represents a * well-formed integer. A well-formed integer consists only of an * optional leading - followed by one or more decimal digits. * Returns true if the given string represents an...
PLEASE DONT COPY FROM INTERNET PLAGIRISM IS PROHIBITED WRITE 2000 WORDS ON THE TOPIC. QUESTION 01:...
PLEASE DONT COPY FROM INTERNET PLAGIRISM IS PROHIBITED WRITE 2000 WORDS ON THE TOPIC. QUESTION 01: World Rankings of UAE and its Implications (REQUIRE 2000 WORDS) 1. Introduction of the topic 2. Review of literature 3. Data, methodology 4. Analysis & Findings of the study 5. Conclusion 6. Reference
Please, write code in c++. Using iostream and cstring library. Your friend is the person who...
Please, write code in c++. Using iostream and cstring library. Your friend is the person who does not like any limitations in the life. And when you said to him that it is totally impossible to work with integer numbers bigger than 4 294 967 296 in C++ he blamed you in time-wasting during the university study.So to prove that you hadn't waste 2 months of your life studying C++ in university you have to solve this issue. Your task...
Write a code using c# Maximum Sub Array.
Write a code using c# Maximum Sub Array.
Please write the code in c++ Write a function with one input parameter that is a...
Please write the code in c++ Write a function with one input parameter that is a vector of strings. The function should count and return the number of strings in the vector that have either an 'x' or a 'z' character in them. For example, when the function is called, if the vector argument contains the 6 string values, "enter", "exit", "zebra", "tiger", "pizza", "zootaxy" the function should return a count of 4. ("exit", "zebra", "pizza", and "zootaxy" all have...
write code to manage a linked list using recursive approach. (Using this code) C++ IN Unix....
write code to manage a linked list using recursive approach. (Using this code) C++ IN Unix. // app.cpp #include <iostream> #include "linkedlist.h" using namespace std; void find(LinkedList& list, char ch) {    if (list.find(ch))        cout << "found ";    else        cout << "did not find ";    cout << ch << endl; } int main() {    LinkedList   list;    list.add('x');    list.add('y');    list.add('z');    cout << list;    find(list, 'y');    list.del('y');    cout...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT