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.

Here is the provided arrayListType.h file. Please also explain where the codes should be as well$($whether its in the $.$h or the $.$cpp and explain why$)$:

the last bit of code from the last page$($also the same bit cut off at the end of page $5)$ is here:

template

void arrayListType::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

removeAt$($loc$)$; $//$exists in the list

else

cout $$ "The item to be deleted is not in the list."

$$ endl;

$\}$

$\}//$end remove

template

arrayListType::arrayListType$($int size$)$

$\{$

if $($size $<mtext\; id="EditorElement\_235091"></mtext><mn\; id="EditorElement\_235092">0</mn><mi\; id="EditorElement\_235093">)</mi>$

$\{$

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

arrayListType::~arrayListType$()$

$\{$

delete$[]$ list;

$\}$

template

arrayListType::arrayListType

$($const arrayListType& 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

const arrayListType& arrayListType::operator$=$

$($const arrayListType& 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;

$\}$