Question

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

Answer 1

ANSWER :-

GIVEN THAT :-

#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;
}

OUTPUT :-