Modify the HeapSort.cpp file to implement the required functions for a heap sort
ID: 3542560 • Letter: M
Question
Modify the HeapSort.cpp file to implement the required functions for a heap sort algorithm.
Once the functions have been implemented, the program will sort and print list of strings in alphabetical
order. The heapSort() function will call the buildHeap() and heapify() functions. The buildHeap()
function will also call the heapify() function. Your program must use these functions.
/**
* HeapSort.cpp - Implementation and test driver for the heap sort algorithm.
*
* TODO: Include your name and course number here.
*/
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
void printItems(string list[], int length);
void heapSort(string list[], int length);
void buildHeap(string list[], int length);
void heapify(string list[], int low, int high);
int main(int argc, char **argv)
{
string stars[] = {
"Sheliak", "Sulafat", "Aladfar", "Al Athfar", "Denebola", "Al Gieba",
"Zozma", "Ras Elased", "Adhafera", "Coxa", "Tsze Tseang", "Alterf",
"Rasalas", "Pollux", "Almeisan", "Wasat", "Mebsuta", "Mekbuda",
"Propus", "Tejat"
};
int numberOfStars = 20;
// Print the unsorted items
cout << "Items unsorted:" << endl;
printItems(stars, numberOfStars);
// Sort the items
heapSort(stars, numberOfStars);
// Print the sorted items
cout << "Items sorted:" << endl;
printItems(stars, numberOfStars);
cout << " ** Press any key to continue ** ";
getchar();
return 0;
}
void printItems(string list[], int length)
{
for (int i=0; i < length; i++)
{
cout << list[i] << endl;
}
cout << endl;
return;
}
void heapSort(string list[], int length)
{
// TODO: Implement the heapSort() function. This funciton will call
// both the buildHeap() and heapify() functions.
}
void buildHeap(string list[], int length)
{
// TODO: Implement the buildHeap() function. This function will call the
// heapify() funciton.
}
void heapify(string list[], int low, int high)
{
// TODO: Implement the heapify() funciton.
}
Explanation / Answer
// the compailed editon for you
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
void printItems(string list[], int length);
void heapSort(string list[], int length);
void buildHeap(string list[], int length);
void heapify(string list[], int low, int high);
int main(int argc, char **argv)
{
string stars[] = {
"Sheliak", "Sulafat", "Aladfar", "Al Athfar", "Denebola", "Al Gieba",
"Zozma", "Ras Elased", "Adhafera", "Coxa", "Tsze Tseang", "Alterf",
"Rasalas", "Pollux", "Almeisan", "Wasat", "Mebsuta", "Mekbuda",
"Propus", "Tejat"
};
int numberOfStars = 20;
cout << "Items unsorted:" << endl;
printItems(stars, numberOfStars);
heapSort(stars, numberOfStars);
cout << "Items sorted:" << endl;
printItems(stars, numberOfStars);
cout << " ** Press any key to continue ** ";
getchar();
return 0;
}
void printItems(string list[], int length)
{
for (int i=0; i < length; i++)
{
cout << list[i] << endl;
}
cout << endl;
return;
}
void heapSort(string list[], int length)
{
// TODO: Implement the heapSort() function. This funciton will call
// both the buildHeap() and heapify() functions.
buildHeap(list, length);
for (int i = length-1; i >= 1; i--)
{
string temp;
temp=list[0];
list[0]=list[i];
list[i]=temp;
heapify(list, 0, i);
}
}
void buildHeap(string list[], int length)
{
// TODO: Implement the buildHeap() function. This function will call the
// heapify() funciton.
for (int i = (length-1)/2; i >= 0; i--)
{
heapify(list, i, length);
}
}
void heapify(string list[], int low, int high)
{
// TODO: Implement the heapify() funciton.
int nL=low*2+1;
int nR=(low+1)*2;
int nLargest;
if (nL < high && list[low] < list[nL])
{
nLargest = nL;
}
else
{
nLargest = low;
}
if (nR < high && list[nLargest] < list[nR])
{
nLargest = nR;
}
if (nLargest != low)
{
string temp;
temp=list[nLargest];
list[nLargest]=list[low];
list[low]=temp;
heapify(list, nLargest, high);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.