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 class provided (arrayListType.h). Ask the user to enter a list of positive integers ending with -999, sort the integers, and display the pivots for each iteration and the sorted array. Main Function #include #include "arrayListType.h" using namespace std; int main() { arrayListType list; int num; cout << "Line 8: Enter numbers ending with -999" << endl; cin >> num; while (num != -999) { list.insert(num); cin >> num; } cout << "Line 15: The list before sorting:" << endl; list.print(); cout << endl; list.selectionSort(); cout << "Line 19: The list after sorting:" << endl; list.print(); cout << endl; return 0; } Header File (arrayList.h) Including images #include #include using namespace std; #ifndef H_arrayListType #define H_arrayListType template class arrayListType { public: const arrayListType& operator= (const arrayListType&); bool isEmpty() const; bool isFull() const; int listSize() const; int maxListSize() const; void print() const; bool isItemAtEqual(int location, const elemType& item) const; void insertAt(int location, const elemType& insertItem); void insertEnd(const elemType& insertItem); void removeAt(int location); void retrieveAt(int location, elemType& retItem) const; void replaceAt(int location, const elemType& repItem); void clearList(); int seqSearch(const elemType& item) const; void insert(const elemType& insertItem); void remove(const elemType& removeItem); arrayListType(int size = 100); arrayListType(const arrayListType& otherList); ~arrayListType(); protected: elemType* list; int length; int maxSize; }; #endif template bool arrayListType::isEmpty() const { return (length == 0); } template bool arrayListType::isFull() const { return (length == maxSize); } template int arrayListType::listSize() const { return length; } template int arrayListType::maxListSize() const { return maxSize; } template void arrayListType::print() const { for (int i = 0; i < length; i++) cout << list[i] << " "; cout << endl; } template bool arrayListType::isItemAtEqual (int location, const elemType& item) const { return(list[location] == item); } template void arrayListType::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) cerr << "Cannot insert in a full list" << endl; else { for (int i = length; i > location; i--) list[i] = list[i - 1]; list[location] = insertItem; length++; } } template void arrayListType::insertEnd(const elemType& insertItem) { if (length >= maxSize) cerr << "Cannot insert in a full list" << endl; else { list[length] = insertItem; length++; } } template void arrayListType::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--; } } template void arrayListType::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 void arrayListType::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 void arrayListType::clearList() { length = 0; }
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 class provided (arrayListType.h). Ask the user to enter a list of positive integers ending with -999, sort the integers, and display the pivots for each iteration and the sorted array.
Main Function
#include <iostream>
#include "arrayListType.h"
using namespace std;
int main()
{
arrayListType<int> list;
int num;
cout << "Line 8: Enter numbers ending with -999" << endl;
cin >> num;
while (num != -999)
{
list.insert(num);
cin >> num;
}
cout << "Line 15: The list before sorting:" << endl;
list.print();
cout << endl;
list.selectionSort();
cout << "Line 19: The list after sorting:" << endl;
list.print();
cout << endl;
return 0;
}
Header File (arrayList.h) Including images
#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>&);
bool isEmpty() const;
bool isFull() const;
int listSize() const;
int maxListSize() const;
void print() const;
bool isItemAtEqual(int location, const elemType& item) const;
void insertAt(int location, const elemType& insertItem);
void insertEnd(const elemType& insertItem);
void removeAt(int location);
void retrieveAt(int location, elemType& retItem) const;
void replaceAt(int location, const elemType& repItem);
void clearList();
int seqSearch(const elemType& item) const;
void insert(const elemType& insertItem);
void remove(const elemType& removeItem);
arrayListType(int size = 100);
arrayListType(const arrayListType<elemType>& otherList);
~arrayListType();
protected:
elemType* list;
int length;
int maxSize;
};
#endif
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)
cerr << "Cannot insert in a full list" << endl;
else
{
for (int i = length; i > location; i--)
list[i] = list[i - 1];
list[location] = insertItem;
length++;
}
}
template <class elemType>
void arrayListType<elemType>::insertEnd(const elemType& insertItem)
{
if (length >= maxSize)
cerr << "Cannot insert in a full list" << endl;
else
{
list[length] = insertItem;
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];
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;
}
![### Understanding Template Classes in C++
The following code demonstrates the use of **template classes** in C++. Template classes allow for type-independent classes and functions, enhancing code flexibility and reusability. Here, an **arrayListType** template class is defined and implemented.
#### 1. Template Class Definition and Constructor
```cpp
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];
}
```
- **template <class elemType>**: Declares a template for the class.
- **arrayListType<elemType>::arrayListType(int size)**: Defines the constructor for the class. If the size provided is negative, it defaults to a size of 100.
- **cerr**: Outputs an error message to the standard error stream.
- **maxSize**: Stores the size of the array.
- **length**: Stores the current length of the array.
- **list**: A pointer to dynamically allocated memory for the array.
#### 2. Destructor
```cpp
template <class elemType>
arrayListType<elemType>::~arrayListType() {
delete[] list;
}
```
- **~arrayListType()**: Destructor that deallocates the memory of the list to avoid memory leaks.
#### 3. Copy Constructor
```cpp
template <class elemType>
arrayListType<elemType>::arrayListType(const arrayListType<elemType>& otherList) {
maxSize = otherList.maxSize;
length = otherList.length;
list = new elemType[maxSize];
assert(list != NULL);
for (int j = 0; j < length; j++) {
list[j] = otherList.list[j];
}
}
```
- **arrayListType(const arrayListType<elemType>& otherList)**: Copy constructor which initializes a new object as a copy of an existing object.
- **assert**: Ensures that memory allocation for **list** was successful.
#### 4. Assignment Operator Overload
```cpp
template <class elemType>
const arrayList](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F90fa3572-bb76-41a3-af93-df6b9e5f000d%2Fbd154110-a49c-4f4e-b86c-966551a12d55%2Fzoi4lhg_processed.png&w=3840&q=75)
![### Understanding Basic List Operations in C++
This section covers essential list operations implemented in C++. The code snippets provided illustrate searching, inserting, and removing elements within an array-based list.
#### 1. Sequential Search (`seqSearch`)
The `seqSearch` function performs a sequential search to locate an element in the list.
```cpp
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;
}
```
- **Parameters**: `item` - the element to search for.
- **Return Value**: Returns the index of the item if found; otherwise, returns -1.
#### 2. Insert Element (`insert`)
The `insert` function adds an element to the list if there is space and the item is not already present.
```cpp
template <class elemType>
void arrayListType<elemType>::insert(const elemType& insertItem) {
int loc;
if (length == 0)
list[length++] = insertItem;
else if (length == maxSize)
cerr << "Cannot insert in a full list." << endl;
else {
loc = seqSearch(insertItem);
if (loc == -1)
list[length++] = insertItem;
else
cerr << "The item to be inserted is already in the list. No duplicates are allowed." << endl;
}
}
```
- **Parameters**: `insertItem` - the element to be added to the list.
- **Functionality**:
- If the list is empty, it adds the element.
- If the list is full, it outputs an error message.
- If the element is not already in the list, it adds the element.
- If the element is already in the list, it outputs an error message.
#### 3. Remove Element (`remove`)
The `remove` function deletes an element from the list if it is present.
```cpp
template <class elemType>
void arrayListType<elemType>::remove(const elemType& removeItem) {
int loc;
if (length ==](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F90fa3572-bb76-41a3-af93-df6b9e5f000d%2Fbd154110-a49c-4f4e-b86c-966551a12d55%2Fsv10ck9_processed.png&w=3840&q=75)
Step by step
Solved in 5 steps with 7 images
