C++ Can someone please make a heap header file with the code that I have. I have

Question

C++

Can someone please make a heap header file with the code that I have. I have the cpp file. Please make a "heap.h" using my code.

Also, this is the assignment, for reference:
Selection Sort and Heap Sort

Create an array of random numbers within the range -99 to 99 of a given size.
Sort it using the selection sort algorithm. Sort the same array using the heap sort algorithm.
If the size of the array is less than or equal to 100, print the arrays before and after sorting (for both selection and heap sort).
Change both algorithms to keep track of the number of data comparisons and data moves.
Save these results. Repeat the process with other arrays. Then write short report to compare the results.

Explanation / Answer

A header file shoul have the minimum practical interface for corresponding .cpp file, the header file can include all the #include , #defines, class declaration, function declaration, struct definition etc but header file should not include any definintion.

So I separated Your code in heap.h file and heap.cpp file, Also I modified your function selecSort()

//changing position of of min and incrementing count
if (arr[j] < arr[posMin])
{
selecComp++;
posMin = j;
}

It was not sorting because your posMin was out of scope of if condition.

Please find the update code.

*************************heap.h*******************

//#include
//#include
//#include
#include<iostream>
#include<time.h>
#include <stdlib.h> //srand

using namespace std;

// Function prototypes
void print(int[], int);
void fill(int[], int);
void selecSort(int[], int);
void heapSort(int[], int);
void heapify(int[], int, int);
void copy1(int[], int[], int);

***********************.cpp************************************

#include "heap.h"
int selecComp = 0, selecMove = 0, heapComp = 0, heapMove = 0;

int main()
{
int arraySize;
cout << "Enter size of array: " << endl;
cin >> arraySize;
cout << " ";

int *randArr1 = new int[arraySize];
int *randArr2 = new int[arraySize];

srand((unsigned)time(NULL));
fill(randArr1, arraySize);
copy1(randArr1, randArr2, arraySize);

if (arraySize <= 100)
{
cout << "Selection sort Unsorted array: " << endl;
print(randArr1, arraySize);
}

selecSort(randArr1, arraySize);

if (arraySize <= 100)
{
cout << " Sorted array: " << endl;
print(randArr1, arraySize);
}

if (arraySize <= 100)
{
cout << " Heap sort Unsorted array: " << endl;
print(randArr2, arraySize);
}

heapSort(randArr2, arraySize);

if (arraySize <= 100)
{
cout << " Sorted array: " << endl;
print(randArr2, arraySize);
}

cout << " Selection sort " << endl;
cout << "Number of comparisons: " << selecComp << endl;
cout << "Number of moves: " << selecMove << endl;
cout << " Heap sort " << endl;
cout << "Number of comparisons: " << heapComp << endl;
cout << "Number of moves: " << heapMove << endl << endl;

return 0;

}

void copy1(int a[], int b[], int arraySize) {

for (int i = 0; i < arraySize; i++)
{
b[i] = a[i];
}
}

void fill(int arr[], int arraySize)
{
for (int i = 0; i < arraySize; i++)
{
arr[i] = -99 + rand() % (99 - (-99) + 1);
}
}

void print(int arr[], int arraySize)
{
for (int i = 0; i < arraySize; i++)
{
cout << arr[i] << " ";
}
}

void selecSort(int arr[], int arraySize)
{
int posMin, temp;

for (int i = 0; i < arraySize - 1; i++)
{
posMin = i; // Sets posMin to the current index of the array

for (int j = i + 1; j < arraySize; j++)
{
//changing position of of min and incrementing count
if (arr[j] < arr[posMin])
{
selecComp++;
posMin = j;
}

// posMin keeps track of the index that min is at, which is needed when a swap happens

}

// A swap must happen when a smaller value has been found, if posMin no longer equals i

if (posMin != i)
{
selecComp++;
temp = arr[i];
arr[i] = arr[posMin];
arr[posMin] = temp;
selecMove++;
}
}
}

void heapSort(int arr[], int n)
{
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

// Heap sort
for (int i = n - 1; i >= 0; i--)

{
swap(arr[0], arr[i]);
heapMove++;
// Heapify root element to get highest element at root again
heapify(arr, i, 0);
}
}

void heapify(int arr[], int n, int i)
{
// Find largest among root, left child and right child
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;

if (l < n && arr[l] > arr[largest])
{
heapComp++;
largest = l;
}

if (r < n && arr[r] > arr[largest])
{
heapComp++;
largest = r;
}

// Swap and continue heapifying if root is not largest
if (largest != i)
{
swap(arr[i], arr[largest]);
heapMove++;
heapify(arr, n, largest);
}
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.