Explore a complete C++ implementation of a dynamic array list using templates with the arrayListType class. This well-structured code includes essential functions for adding, removing, retrieving, replacing, and searching elements, along with utilities for printing, clearing, and managing the list size. Perfect for academic projects and advanced programming applications—includes detailed comments and ready-to-use functions for efficient list management in C++.
Question 1 (25 pts):
Assume the following list of keys:
49, 4, 89, 25, 67, 46, 83, 30, 60, 22, 12
This list is to be sorted using the quick sort algorithm as discussed in this chapter. Use pivot as the middleelement of the list, and fill in the blank squares below.
pivotpivot pivotpivot pivot pivot pivotpivot pivotpivot pivot
49, 4, 89, 25, 67, 46, 83, 30, 60, 22, 12
Question 2 (25 pts):
Assume the following list of keys:
32, 47, 3, 28, 92, 7, 87, 37, 22, 43, 40, 74, 13, 35, 51
This list is to be sorted using the merge sort algorithm as discussed in this chapter. Fill in the blank squaresbelow.
32, 47, 3, 28, 92, 7, 87, 37, 22, 43, 40, 74, 13, 35, 51
Question 3 (25 pts):
Assume the following list:
32, 47, 3, 28, 92, 7, 87, 37, 22, 43, 40, 74, 13, 35, 51, 14, 26, 5
(a) Using the function buildHeap as given in this chapter, convert the list into a heap.
(b) Show the resulting list after three passes of heapsort. (Use the heapify procedure as given in this chapter.)
One pass:
Two passes:
Three passes:
Question 4 (25 pts):
Modify the quick sort implementation in the textbook to sort the array using pivot as the median of the first, last, and middle elements of the array. Add the modified quick sort implementation to the arrayListType classprovided (arrayListType.h). Ask the user to enter a list of positive integers ending with -999, sort the integers, anddisplay the pivots for each iteration and the sorted array.
Submit the source code, and copy and paste the screenshot of the output here.
The code:
#include <iostream>
#include <cassert>
using namespace std;
#ifndef H_arrayListType
#define H_arrayListType
template <class elemType>
class arrayListType {
public:
const arrayListType<elemType>& operator=(const arrayListType<elemType>&); // Overloads the assignment operator
bool isEmpty() const; // Function to determine whether the list is empty
bool isFull() const; // Function to determine whether the list is full
int listSize() const; // Function to determine the number of elements in the list
int maxListSize() const; // Function to determine the size of the list
void print() const; // Function to output the elements of the list
bool isItemAtEqual(int location, const elemType& item) const; // Compare item at location
void insertAt(int location, const elemType& insertItem); // Insert at location
void insertEnd(const elemType& insertItem); // Insert at end
void removeAt(int location); // Remove item at location
void retrieveAt(int location, elemType& retItem) const; // Retrieve item at location
void replaceAt(int location, const elemType& repItem); // Replace item at location
void clearList(); // Remove all elements from the list
int seqSearch(const elemType& item) const; // Sequential search
void insert(const elemType& insertItem); // Insert if not duplicate
void remove(const elemType& removeItem); // Remove by value
arrayListType(int size = 100); // Constructor
arrayListType(const arrayListType<elemType>& otherList); // Copy constructor
~arrayListType(); // Destructor
protected:
elemType* list; // Array to hold the list elements
int length; // Number of elements in the list
int maxSize; // Maximum size of the list
};
#endif
// Function Definitions
template <class elemType>
bool arrayListType<elemType>::isEmpty() const {
return (length == 0);
}
template <class elemType>
bool arrayListType<elemType>::isFull() const {
return (length == maxSize);
}
template <class elemType>
int arrayListType<elemType>::listSize() const {
return length;
}
template <class elemType>
int arrayListType<elemType>::maxListSize() const {
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) const {
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
}
}
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
}
}
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]; // move the elements up
length--;
}
}
template <class elemType>
void arrayListType<elemType>::retrieveAt(int location, elemType& retItem) const {
if (location < 0 || location >= length)
cerr << "The location of the item to be retrieved is out of range." << endl;
else
retItem = list[location];
}
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;
}
template <class elemType>
void arrayListType<elemType>::clearList() {
length = 0;
}
template <class elemType>
int arrayListType<elemType>::seqSearch(const elemType& item) const {
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;
}
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;
}
}
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) // the item to be removed exists in the list
removeAt(loc);
else
cout << "The item to be deleted is not in the list." << endl;
}
}
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); // In C++, new throws bad_alloc if it fails
}
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];
}
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;
}
Solution
Question 1: Quick Sort (Pivot = Middle Element Each Time)
Given List:
49, 4, 89, 25, 67, 46, 83, 30, 60, 22, 12
Step 1: First Call
-
List: 49, 4, 89, 25, 67, 46, 83, 30, 60, 22, 12
-
Middle index: 5 (0-based), Pivot = 46
Partition:
-
Elements < 46: 4, 25, 30, 22, 12
-
Pivot: 46
-
Elements > 46: 49, 89, 67, 83, 60
Result:
[4, 25, 30, 22, 12], 46, [49, 89, 67, 83, 60]
Step 2: Left Sublist (4, 25, 30, 22, 12)
-
Middle index: 2, Pivot = 30
-
Partition:
-
<30: 4, 25, 22, 12
-
Pivot: 30
-
30: (none)
-
Result:
[4, 25, 22, 12], 30
Step 3: Left Sublist of (4, 25, 22, 12)
-
Middle index: 2, Pivot = 22
-
Partition:
-
<22: 4, 12
-
Pivot: 22
-
22: 25
-
Result:
[4, 12], 22, 25
Step 4: Left Sublist of (4, 12)
-
Middle index: 1, Pivot = 12
-
Partition:
-
<12: 4
-
Pivot: 12
-
12: (none)
-
Now we have: 4, 12
Now combine back:
Sorted left side: 4, 12, 22, 25, 30
Step 2 (Right Sublist): (49, 89, 67, 83, 60)
-
Middle index: 2, Pivot = 67
-
Partition:
-
<67: 49, 60
-
Pivot: 67
-
67: 89, 83
-
Result:
[49, 60], 67, [89, 83]
Step 3: Left Sublist of (49, 60)
-
Middle index: 1, Pivot = 60
-
Partition:
-
<60: 49
-
Pivot: 60
-
Now: 49, 60
Step 3: Right Sublist of (89, 83)
-
Middle index: 1, Pivot = 83
-
Partition:
-
<83: (none)
-
Pivot: 83
-
83: 89
-
Now: 83, 89
Now combine back:
Sorted right side: 49, 60, 67, 83, 89
Final Sorted List:
4, 12, 22, 25, 30, 46, 49, 60, 67, 83, 89
Question 2: Merge Sort
Given List:
32, 47, 3, 28, 92, 7, 87, 37, 22, 43, 40, 74, 13, 35, 51
Step-by-step Merge Sort breakdown:
Splits:
-
[32, 47, 3, 28, 92, 7, 87, 37] and [22, 43, 40, 74, 13, 35, 51]
-
Continue splitting until single elements, then merge upwards.
After all merges:
Final sorted list:
3, 7, 13, 22, 28, 32, 35, 37, 40, 43, 47, 51, 74, 87, 92
Question 3: Heap Sort
List:
32, 47, 3, 28, 92, 7, 87, 37, 22, 43, 40, 74, 13, 35, 51, 14, 26, 5
(a) Build Heap
Max Heap after buildHeap:
92, 47, 87, 37, 51, 74, 35, 32, 22, 43, 40, 7, 13, 3, 28, 14, 26, 5
(b) Three Passes of Heapsort
-
One Pass:
-
Swap first and last: 5, ..., 92
-
Heapify root (length-1):
87, 47, 74, 37, 51, 40, 35, 32, 22, 43, 5, 7, 13, 3, 28, 14, 26, 92
-
Two Passes:
-
Swap first and (last-1): 26, ..., 92, 87
-
Heapify root (length-2):
74, 47, 51, 37, 26, 40, 35, 32, 22, 43, 5, 7, 13, 3, 28, 14, 87, 92
-
Three Passes:
-
Swap first and (last-2): 14, ..., 92, 87, 74
-
Heapify root (length-3):
51, 47, 40, 37, 26, 28, 35, 32, 22, 43, 5, 7, 13, 3, 14, 74, 87, 92
Question 4: Modified Quick Sort Implementation
Request
Modify the quick sort algorithm to use the median of the first, last, and middle elements as the pivot.
Add to arrayListType class.
Ask user to enter integers ending with -999, show pivots at each iteration and final sorted array.
Sample Code Outline
// Add this function inside arrayListType<T>
void quickSortMedianPivot(int low, int high) {
if (low < high) {
int pivotIndex = medianOfThree(low, high);
// Swap pivot to end
swap(list[pivotIndex], list[high]);
int p = partition(low, high);
cout << "Pivot: " << list[p] << endl; // Print pivot value
quickSortMedianPivot(low, p - 1);
quickSortMedianPivot(p + 1, high);
}
}
int medianOfThree(int low, int high) {
int mid = (low + high) / 2;
int a = list[low], b = list[mid], c = list[high];
if ((a > b) != (a > c)) return low;
else if ((b > a) != (b > c)) return mid;
else return high;
}
int partition(int low, int high) {
int pivot = list[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (list[j] < pivot) {
i++;
swap(list[i], list[j]);
}
}
swap(list[i + 1], list[high]);
return i + 1;
}
User Input and Output Example: