Write a program to test heapsort for array-based lists. Please review my code be
ID: 3560202 • Letter: W
Question
Write a program to test heapsort for array-based lists.
Please review my code below and tell me where I am going wrong. I'm guessing it is somewhere in the header? Any help is appreciated! Thank you
#ifndef H_arrayListType
#define H_arrayListType
#include <iostream>
#include <cassert>
using namespace std;
template <class elemType>
class arrayListType
{
public:
const arrayListType<elemType>& operator=
(const arrayListType<elemType>&);
bool isEmpty();
bool isFull();
int listSize();
int maxListSize();
void print() const;
bool isItemAtEqual(int location, const elemType& item);
void insertAt(int location, const elemType& insertItem);
void insertEnd(const elemType& insertItem);
void removeAt(int location);
void retrieveAt(int location, elemType& retItem);
void replaceAt(int location, const elemType& repItem);
void clearList();
int seqSearch(const elemType& item);
void insert(const elemType& insertItem);
void remove(const elemType& removeItem);
arrayListType(int size = 100);
arrayListType(const arrayListType<elemType>& otherList);
~arrayListType();
void selectionSort();
void heapSort();
protected:
elemType *list; //array to hold the list elements
int length; //to store the length of the list
int maxSize; //to store the maximum size of the list
void swap(int first, int second);
int minLocation(int first, int last);
void heapify(int low, int high);
void buildHeap();
};
template<class elemType>
void arrayListType<elemType>::heapify(int low, int high)
{
int largeIndex;
elemType temp = list[low]; //copy the root node of the subtree
largeIndex = 2 * low + 1; //index of the left child
while (largeIndex <= high)
{
if (largeIndex < high)
if (list[largeIndex] < list[largeIndex + 1])
largeIndex = largeIndex + 1; //index of the
//largest child
if (temp > list[largeIndex]) //subtree is already in a heap
break;
else
{
list[low] = list[largeIndex]; //move the larger child
//to the root
low = largeIndex; //go to the subtree to
//restore the heap
largeIndex = 2 * low + 1;
}
}//end while
list[low] = temp; //insert temp into the tree, that is, list
} //end heapify
template<class elemType>
void arrayListType<elemType>::buildHeap()
{
int index;
for (index = length / 2 - 1; index >= 0; index--)
heapify(index, length - 1);
}
template<class elemType>
void arrayListType<elemType>::heapSort()
{
int lastOutOfOrder;
elemType temp;
buildHeap();
for (lastOutOfOrder = length - 1; lastOutOfOrder >= 0;
lastOutOfOrder--)
{
temp = list[lastOutOfOrder];
list[lastOutOfOrder] = list[0];
list[0] = temp;
heapify(0, lastOutOfOrder - 1);
}//end for
}//end heapSort
template <class elemType>
bool arrayListType<elemType>::isEmpty()
{
return (length == 0);
}
template <class elemType>
bool arrayListType<elemType>::isFull()
{
return (length == maxSize);
}
template <class elemType>
int arrayListType<elemType>::listSize()
{
return length;
}
template <class elemType>
int arrayListType<elemType>::maxListSize()
{
return maxSize;
}
template <class elemType>
void arrayListType<elemType>::print() const
{
for (int i = 0; i < length; i++)
cout << list[i] << " ";
cout << endl;
}
template <class elemType>
bool arrayListType<elemType>::isItemAtEqual
(int location, const elemType& item)
{
return(list[location] == item);
}
template <class elemType>
void arrayListType<elemType>::insertAt
(int location, const elemType& insertItem)
{
if (location < 0 || location >= maxSize)
cerr << "The position of the item to be inserted "
<< "is out of range" << endl;
else
if (length >= maxSize) //list is full
cerr << "Cannot insert in a full list" << endl;
else
{
for (int i = length; i > location; i--)
list[i] = list[i - 1]; //move the elements down
list[location] = insertItem; //insert the item at the
//specified position
length++; //increment the length
}
} //end insertAt
template <class elemType>
void arrayListType<elemType>::insertEnd(const elemType& insertItem)
{
if (length >= maxSize) //the list is full
cerr << "Cannot insert in a full list" << endl;
else
{
list[length] = insertItem; //insert the item at the end
length++; //increment the length
}
} //end insertEnd
template <class elemType>
void arrayListType<elemType>::removeAt(int location)
{
if (location < 0 || location >= length)
cerr << "The location of the item to be removed "
<< "is out of range" << endl;
else
{
for (int i = location; i < length - 1; i++)
list[i] = list[i + 1];
length--;
}
} //end removeAt
template <class elemType>
void arrayListType<elemType>::retrieveAt
(int location, elemType& retItem)
{
if (location < 0 || location >= length)
cerr << "The location of the item to be retrieved is "
<< "out of range." << endl;
else
retItem = list[location];
} //end retrieveAt
template <class elemType>
void arrayListType<elemType>::replaceAt
(int location, const elemType& repItem)
{
if (location < 0 || location >= length)
cerr << "The location of the item to be replaced is "
<< "out of range." << endl;
else
list[location] = repItem;
} //end replaceAt
template <class elemType>
void arrayListType<elemType>::clearList()
{
length = 0;
} //end clearList
template <class elemType>
int arrayListType<elemType>::seqSearch(const elemType& item)
{
int loc;
bool found = false;
for (loc = 0; loc < length; loc++)
if (list[loc] == item)
{
found = true;
break;
}
if (found)
return loc;
else
return -1;
} //end seqSearch
template <class elemType>
void arrayListType<elemType>::insert(const elemType& insertItem)
{
int loc;
if (length == 0) //list is empty
list[length++] = insertItem; //insert the item and
//increment the length
else if (length == maxSize)
cerr << "Cannot insert in a full list." << endl;
else
{
loc = seqSearch(insertItem);
if (loc == -1) //the item to be inserted
//does not exist in the list
list[length++] = insertItem;
else
cerr << "the item to be inserted is already in "
<< "the list. No duplicates are allowed." << endl;
}
} //end insert
template<class elemType>
void arrayListType<elemType>::remove(const elemType& removeItem)
{
int loc;
if (length == 0)
cerr << "Cannot delete from an empty list." << endl;
else
{
loc = seqSearch(removeItem);
if (loc != -1)
removeAt(loc);
else
cout << "The item to be deleted is not in the list."
<< endl;
}
} //end remove
template <class elemType>
arrayListType<elemType>::arrayListType(int size)
{
if (size < 0)
{
cerr << "The array size must be positive. Creating "
<< "an array of size 100. " << endl;
maxSize = 100;
}
else
maxSize = size;
length = 0;
list = new elemType[maxSize];
assert(list != NULL);
}
template <class elemType>
arrayListType<elemType>::~arrayListType()
{
delete[] list;
}
template <class elemType>
arrayListType<elemType>::arrayListType
(const arrayListType<elemType>& otherList)
{
maxSize = otherList.maxSize;
length = otherList.length;
list = new elemType[maxSize]; //create the array
assert(list != NULL); //terminate if unable to allocate
//memory space
for (int j = 0; j < length; j++) //copy otherList
list[j] = otherList.list[j];
} //end copy constructor
template <class elemType>
const arrayListType<elemType>& arrayListType<elemType>::operator=
(const arrayListType<elemType>& otherList)
{
if (this != &otherList) //avoid self-assignment
{
delete[] list;
maxSize = otherList.maxSize;
length = otherList.length;
list = new elemType[maxSize]; //create the array
assert(list != NULL); //if unable to allocate memory
//space, terminate the program
for (int i = 0; i < length; i++)
list[i] = otherList.list[i];
}
return *this;
}
template <class elemType>
void arrayListType<elemType>::selectionSort()
{
int minIndex;
for (int loc = 0; loc < length - 1; loc++)
{
minIndex = minLocation(loc, length - 1);
swap(loc, minIndex);
}
}
template <class elemType>
int arrayListType<elemType>::minLocation(int first, int last)
{
int minIndex;
minIndex = first;
for (int loc = first + 1; loc <= last; loc++)
if (list[loc] < list[minIndex])
minIndex = loc;
return minIndex;
} //end minLocation
template <class elemType>
void arrayListType<elemType>::swap(int first, int second)
{
elemType temp;
temp = list[first];
list[first] = list[second];
list[second] = temp;
}//end swap
#endif
/*Write a program to test heapsort for array-based lists as given in this chapter*/
#include "stdafx.h"
#include "arrayListType.h"
#include <iostream>
using namespace std;
int main()
{
int value;
arrayListType heapList;
cout << "Enter the integers" << endl;
cin >> value;
while (value != -999)
{
heapList.insert(value);
cin >> value;
}
cout << "The integers before sorting" << endl;
heapList.print();
heapList.heapSort();
cout << "The integers after sorting" << endl;
heapList.print();
system("pause");
return 0;
}
Explanation / Answer
/*You mistakes are bolded lined here*/
/*arrayListType.h*/
#ifndef H_arrayListType
#define H_arrayListType
#include <iostream>
#include <cassert>
using namespace std;
template <class elemType>
class arrayListType
{
public:
const arrayListType<elemType>& operator=
(const arrayListType<elemType>&);
bool isEmpty();
bool isFull();
int listSize();
int maxListSize();
void print() const;
bool isItemAtEqual(int location, const elemType& item);
void insertAt(int location, const elemType& insertItem);
void insertEnd(const elemType& insertItem);
void removeAt(int location);
void retrieveAt(int location, elemType& retItem);
void replaceAt(int location, const elemType& repItem);
void clearList();
int seqSearch(const elemType& item);
void insert(const elemType& insertItem);
void remove(const elemType& removeItem);
arrayListType(int size = 100);
arrayListType(const arrayListType<elemType>& otherList);
~arrayListType();
void selectionSort();
void heapSort();
protected:
elemType *list; //array to hold the list elements
int length; //to store the length of the list
int maxSize; //to store the maximum size of the list
void swap(int first, int second);
int minLocation(int first, int last);
void heapify(int low, int high);
void buildHeap();
};
template<class elemType>
void arrayListType<elemType>::heapify(int low, int high)
{
int largeIndex;
elemType temp = list[low]; //copy the root node of the subtree
largeIndex = 2 * low + 1; //index of the left child
while (largeIndex <= high)
{
if (largeIndex < high)
if (list[largeIndex] < list[largeIndex + 1])
largeIndex = largeIndex + 1; //index of the
//largest child
if (temp > list[largeIndex]) //subtree is already in a heap
break;
else
{
list[low] = list[largeIndex]; //move the larger child
//to the root
low = largeIndex; //go to the subtree to
//restore the heap
largeIndex = 2 * low + 1;
}
}//end while
list[low] = temp; //insert temp into the tree, that is, list
} //end heapify
template<class elemType>
void arrayListType<elemType>::buildHeap()
{
int index;
for (index = length / 2 - 1; index >= 0; index--)
heapify(index, length - 1);
}
template<class elemType>
void arrayListType<elemType>::heapSort()
{
int lastOutOfOrder;
elemType temp;
buildHeap();
for (lastOutOfOrder = length - 1; lastOutOfOrder >= 0;
lastOutOfOrder--)
{
temp = list[lastOutOfOrder];
list[lastOutOfOrder] = list[0];
list[0] = temp;
heapify(0, lastOutOfOrder - 1);
}//end for
}//end heapSort
template <class elemType>
bool arrayListType<elemType>::isEmpty()
{
return (length == 0);
}
template <class elemType>
bool arrayListType<elemType>::isFull()
{
return (length == maxSize);
}
template <class elemType>
int arrayListType<elemType>::listSize()
{
return length;
}
template <class elemType>
int arrayListType<elemType>::maxListSize()
{
return maxSize;
}
template <class elemType>
void arrayListType<elemType>::print() const
{
for (int i = 0; i < length; i++)
cout << list[i] << " ";
cout << endl;
}
template <class elemType>
bool arrayListType<elemType>::isItemAtEqual
(int location, const elemType& item)
{
return(list[location] == item);
}
template <class elemType>
void arrayListType<elemType>::insertAt
(int location, const elemType& insertItem)
{
if (location < 0 || location >= maxSize)
cerr << "The position of the item to be inserted "
<< "is out of range" << endl;
else
if (length >= maxSize) //list is full
cerr << "Cannot insert in a full list" << endl;
else
{
for (int i = length; i > location; i--)
list[i] = list[i - 1]; //move the elements down
list[location] = insertItem; //insert the item at the
//specified position
length++; //increment the length
}
} //end insertAt
template <class elemType>
void arrayListType<elemType>::insertEnd(const elemType& insertItem)
{
if (length >= maxSize) //the list is full
cerr << "Cannot insert in a full list" << endl;
else
{
list[length] = insertItem; //insert the item at the end
length++; //increment the length
}
} //end insertEnd
template <class elemType>
void arrayListType<elemType>::removeAt(int location)
{
if (location < 0 || location >= length)
cerr << "The location of the item to be removed "
<< "is out of range" << endl;
else
{
for (int i = location; i < length - 1; i++)
list[i] = list[i + 1];
length--;
}
} //end removeAt
template <class elemType>
void arrayListType<elemType>::retrieveAt
(int location, elemType& retItem)
{
if (location < 0 || location >= length)
cerr << "The location of the item to be retrieved is "
<< "out of range." << endl;
else
retItem = list[location];
} //end retrieveAt
template <class elemType>
void arrayListType<elemType>::replaceAt
(int location, const elemType& repItem)
{
if (location < 0 || location >= length)
cerr << "The location of the item to be replaced is "
<< "out of range." << endl;
else
list[location] = repItem;
} //end replaceAt
template <class elemType>
void arrayListType<elemType>::clearList()
{
length = 0;
} //end clearList
template <class elemType>
int arrayListType<elemType>::seqSearch(const elemType& item)
{
int loc;
bool found = false;
for (loc = 0; loc < length; loc++)
if (list[loc] == item)
{
found = true;
break;
}
if (found)
return loc;
else
return -1;
} //end seqSearch
template <class elemType>
void arrayListType<elemType>::insert(const elemType& insertItem)
{
int loc;
if (length == 0) //list is empty
list[length++] = insertItem; //insert the item and
//increment the length
else if (length == maxSize)
cerr << "Cannot insert in a full list." << endl;
else
{
loc = seqSearch(insertItem);
if (loc == -1) //the item to be inserted
//does not exist in the list
list[length++] = insertItem;
else
cerr << "the item to be inserted is already in "
<< "the list. No duplicates are allowed." << endl;
}
} //end insert
template<class elemType>
void arrayListType<elemType>::remove(const elemType& removeItem)
{
int loc;
if (length == 0)
cerr << "Cannot delete from an empty list." << endl;
else
{
loc = seqSearch(removeItem);
if (loc != -1)
removeAt(loc);
else
cout << "The item to be deleted is not in the list."
<< endl;
}
} //end remove
template <class elemType>
arrayListType<elemType>::arrayListType(int size)
{
if (size < 0)
{
cerr << "The array size must be positive. Creating "
<< "an array of size 100. " << endl;
maxSize = 100;
}
else
maxSize = size;
length = 0;
list = new elemType[maxSize];
assert(list != NULL);
}
template <class elemType>
arrayListType<elemType>::~arrayListType()
{
delete[] list;
}
template <class elemType>
arrayListType<elemType>::arrayListType
(const arrayListType<elemType>& otherList)
{
maxSize = otherList.maxSize;
length = otherList.length;
list = new elemType[maxSize]; //create the array
assert(list != NULL); //terminate if unable to allocate
//memory space
for (int j = 0; j < length; j++) //copy otherList
list[j] = otherList.list[j];
} //end copy constructor
template <class elemType>
const arrayListType<elemType>& arrayListType<elemType>::operator=
(const arrayListType<elemType>& otherList)
{
if (this != &otherList) //avoid self-assignment
{
delete[] list;
maxSize = otherList.maxSize;
length = otherList.length;
list = new elemType[maxSize]; //create the array
assert(list != NULL); //if unable to allocate memory
//space, terminate the program
for (int i = 0; i < length; i++)
list[i] = otherList.list[i];
}
return *this;
}
template <class elemType>
void arrayListType<elemType>::selectionSort()
{
int minIndex;
for (int loc = 0; loc < length - 1; loc++)
{
minIndex = minLocation(loc, length - 1);
swap(loc, minIndex);
}
}
template <class elemType>
int arrayListType<elemType>::minLocation(int first, int last)
{
int minIndex;
minIndex = first;
for (int loc = first + 1; loc <= last; loc++)
if (list[loc] < list[minIndex])
minIndex = loc;
return minIndex;
} //end minLocation
template <class elemType>
void arrayListType<elemType>::swap(int first, int second)
{
elemType temp;
temp = list[first];
list[first] = list[second];
list[second] = temp;
}//end swap
#endif
/*Write a program to test heapsort for array-based lists as given in this chapter*/
/*main.cpp*/
#include "arrayListType.h"
#include <iostream>
#include<stdlib.h>
using namespace std;
int main()
{
int value;
arrayListType<int> heapList;
cout << "Enter the integers" << endl;
cin >> value;
while (value != -999)
{
heapList.insert(value);
cin >> value;
}
cout << "The integers before sorting" << endl;
heapList.print();
heapList.heapSort();
cout << "The integers after sorting" << endl;
heapList.print();
system("pause");
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.