Question

In this lab, you will implement Heap Sort algorithm in C++ and Report the number of steps and the CPU running time in a table, please show the code and output

Approximation the constant c in the complexity of heap sort (cnlgn) by inspecting the results

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].

Answer 1

C++ Program:

#include <iostream>
#include <chrono>
#include <algorithm>
#include <random>
#include <ctime>
using namespace std;
using namespace std::chrono;
int steps;
void swap(int &x,int &y)
{
  int t=x;
  x=y;
  y=t;
}
void heapify(int i,int *arr,int n)
{
  int l=i;
  if(2*i+1<n)
  {
    if(arr[2*i+1]>arr[l])
    {
      l=2*i+1;
    }
  }
  if(2*i+2<n)
  {
    if(arr[2*i+2]>arr[l])
    {
      l=2*i+2;
    }
  }
  if(l!=i)
  {
    steps++;
    //cout<<1<<endl;
    swap(arr[l],arr[i]);
    heapify(l,arr,n);
  }
}
void heapSort(int arr[], int n) 
{ 
    for(int i=n/2-1;i>=0;i--) 
    {
        heapify(i,arr, n); 
    } 
    for (int i=n-1; i>0; i--) 
    { 
        steps++;
        swap(arr[0], arr[i]); 
        heapify(0,arr, i); 
    } 
} 
int main() {
  int n[]={100,200,300,400,500,1000,4000,10000};
  cout<<"------------------------------------------------------------------------"<<endl;
  cout<<"Count\t\t\tArrangement\t\t\t   Steps\t\tTime(Micro Seconds)\n";
  cout<<"------------------------------------------------------------------------"<<endl;
  for(int i=0;i<8;i++)
  {
    int nn=n[i];
    //already sorted
    steps=0;
    int arr[nn];
    for(int i=0;i<nn;i++)
    {
      arr[i]=i+1;
    }
    auto start=high_resolution_clock::now(); 
    heapSort(arr,nn);
    auto stop=high_resolution_clock::now(); 
    auto duration = duration_cast<microseconds>(stop-start); 
    cout<<nn<<" \t\t\t"<<"Already Sorted  \t\t"<<steps<<" \t\t"<<duration.count()<<endl;
    //reversely sorted
    steps=0;
    for(int i=0;i<nn;i++)
    {
      arr[i]=nn-i;
    }
    start=high_resolution_clock::now(); 
    heapSort(arr,nn);
    stop=high_resolution_clock::now(); 
    duration = duration_cast<microseconds>(stop-start); 
    cout<<nn<<" \t\t\t"<<"Reversely Sorted\t\t"<<steps<<" \t\t"<<duration.count()<<endl;
    //randomly arranged
    steps=0;
    unsigned seed=0;
    shuffle(arr,arr+nn,default_random_engine(seed));
    start=high_resolution_clock::now(); 
    heapSort(arr,nn);
    stop=high_resolution_clock::now(); 
    duration = duration_cast<microseconds>(stop-start); 
    cout<<nn<<" \t\t\t"<<"Randomly Arranged\t\t"<<steps<<" \t\t"<<duration.count()<<endl;
    //Random 50 instance
    steps=0;
    srand(time(0));
    for(int i=0;i<50;i++)
    {
      arr[i]=rand()%nn+1;
    }
    start=high_resolution_clock::now(); 
    heapSort(arr,50);
    stop=high_resolution_clock::now(); 
    duration = duration_cast<microseconds>(stop-start); 
    cout<<nn<<" \t\t\t"<<"Random 50 Instance\t\t"<<steps<<" \t\t"<<duration.count()<<endl;
    cout<<"------------------------------------------------------------------------"<<endl;
  }
}

Sample Output: