Code:
#include <iostream>
#include <iomanip>
#include <cstdlib>
using namespace std;
int operationsCounter=0;
void maxheapify(int A[], int i, int len)
{
int l=2*i;
int r=2*i+1;
int largest, exchange;
if ((l<=len) && (A[l]>A[i]))
{
largest=l;
operationsCounter++;
}
else
{
largest=i;
operationsCounter++;
}
operationsCounter++;
if ((r<=len) && (A[r]>A[largest]))
{
largest=r;
operationsCounter++;
}
operationsCounter++;
if (largest!=i)
{
exchange=A[largest];
A[largest]=A[i];
A[i]=exchange;
maxheapify(A, largest, len);
operationsCounter+=4;
}
operationsCounter++;
//return (A);
}
int main()
{
int exchange, len, option, fakelen;
cout << "How big of an array do you want to sort? " << endl;
cin >> len;
int A[len];
cout << "To have " << len << " numbers generated randomly please enter 1, to enter the array yourself please enter 2: " << endl;
cin >> option;
if (option == 1)
{
for (int i=0; i<len; i++)
{
A[i]=rand();
operationsCounter++;
}
}
else if (option == 2)
{
cout << "Enter the array: " << endl;
for (int i=0; i<len; i++)
{
cin >> A[i];
operationsCounter++;
}
}
else
{
cout << "You didn't enter 1 or 2. What a fool. Restart the program if you must." << endl;
}
cout << "The array before sorting: ";
for(int i=0; i<len; i++)
cout << A[i] << " ";
cout << endl;
fakelen=len;
for(int i=len; i>1; i--)
{
fakelen--;
exchange=A[1];
A[1]=A[i];
A[i]=exchange;
maxheapify(A, 1, fakelen);
}
cout << "The array after sorting: ";
for(int i=0; i<len; i++)
cout << A[i] << " ";
cout << endl << "The approximate number of operations for an array of size " << len << " is: " << operationsCounter << endl;
return 0;
}