Code and comments for each line of code please. Please put the responses for Part $2$ in Markdown format.

For this assignment, implement a radix sort in header file radix.h$.$ A test program is included, sorttest$4.$cpp$,$ that creates an array of integers each no more than $5$ digits $($like $5$ digit zip codes$).$ Your implementation need not be a template function $,$ since it will specifically work with integers. Further, you do not need to accommodate a custom comparison function that is not applicable. An empty function implementation is included in the starter code. Although not required for this assignment, you might consider using vectors for your buckets, as vectors are abstractions of dynamic arrays and easier to work with than ordinary arrays $($the first parameter to the sort function however must remain as an array$).$Use the vector member function push$\_$back to add an integer to a vector. You can clear $($empty$)$ a bucket with the clear member function.

Be sure to change the include file at line $20$ of sorttest$4.$cpp to use your radix.h header file. The starter code given uses quick.h$.$

Part $2$:

Include your responses for this part in RESPONSES.md in Markdown format. Run some timing tests for both Quicksort and Radix Sort. $($Of course you need to change the include file at line $20$ in sorttest$4.$cpp to change algorithms.$)$ Include the results of your tests when submitting this assignment. Be sure to use a progression of array sizes to get a good feel for how they compare. How do the two sorting algorithms compare as the size of the array grows?

What is the run$-$time complexity of this algorithm? What is the run$-$time complexity when you consider that the values to be sorted are specifically $5$ digits or fewer? Do you consider it to be linear, logarithmic, N log N$,$ quadratic, or something else?

radix.h :

#include

#include

void sort $($int a$[],$ size$\_$t n$)\{$

$\}$

quick.h :

#pragma once

#include

template

inline bool sort$\_$compare $($const T& a$,$ const T& b$)\{$ return a $<$ b; $\}$

template

size$\_$t sort$\_$partition $($T a$[],$ size$\_$t low, size$\_$t high, size$\_$t pivot, U cmp$)\{$

int pivot$\_$value $=$ a$[$pivot$]$;

std::swap$($a$[$pivot$],$ a$[$high$])$;

pivot $=$ low;

for $($size$\_$t i $=$ low; i $<$ high; i$++)\{$

if $($cmp$($a$[$i$],$ pivot$\_$value$))$

std::swap$($a$[$i$],$ a$[$pivot$++])$;

$\}$

std::swap$($a$[$pivot$],$ a$[$high$])$;

return pivot;

$\}$

template

void sort $($T a$[],$ size$\_$t low, size$\_$t high, U cmp$)\{$

if $($low $<$ high$)\{$

size$\_$t pivot $=($low $+$ high$)/2$;

pivot $=$ sort$\_$partition$($a$,$ low, high, pivot, cmp$)$;

if $($pivot $>$ low$)$

sort$($a$,$ low, pivot $-1,$ cmp$)$;

if $($pivot $<$ high$)$

sort$($a$,$ pivot $+1,$ high, cmp$)$;

$\}$

$\}$

template

void sort $($T a$[],$ size$\_$t n$,$ U cmp$)\{$ sort$($a$,0,$ n $-1,$ cmp$)$; $\}$

template

void sort $($T a$[],$ size$\_$t n$)\{$ sort$($a$,$ n$,$ sort$\_$compare$)$; $\}$

sorttest$4.$cpp :

#include

#include

#include

#include

using namespace std;

$//$ TODO: Change the include to "radix.h$"$ to use your radix sort implementation.

#include "quick.h$"$

int checksum$1($int a$[],$ int n$)$;

int checksum$2($int a$[],$ int n$)$;

void print$($int a$[],$ int n$)$;

bool is$\_$sorted$($int a$[],$ int n$)$;

int main$($int argc, char$*$ argv$[])\{$

int$*$ x;

int size;

srand$($time$(0))$;

if $(!($size $=$ argc $>1?$ atoi$($argv$[1])$ : $0))\{$

cout $<<$ "Enter array size: $"$;

cin $>>$ size;

$\}$

bool verbose $=$ size $<=120$;

x $=$ new int$[$size$]$;

for $($int i $=0$; i $<$ size; i$++)$

x$[$i$]=$ rand$()\%100000$;

int cksum$1$a $=$ checksum$1($x$,$ size$)$;

int cksum$2$a $=$ checksum$2($x$,$ size$)$;

if $($verbose$)\{$

cout $<<$ endl $<<$ "Before sort:" $<<$ endl;

print$($x$,$ size$)$;

cout $<<"$ Checksums: $"<<$ cksum$1$a $<<""<<$ cksum$2$a $<<$ endl $<<$ endl;

$\}$

cout $<<$ "Sorting... $"$;

cout.flush$()$;

clock$\_$t t $=$ clock$()$;

sort$($x$,$ size$)$;

t $=$ clock$()-$ t;

int cksum$1$b $=$ checksum$1($x$,$ size$)$;

int cksum$2$b $=$ checksum$2($x$,$ size$)$;

cout $<<($is$\_$sorted$($x$,$ size$)$ && cksum$1$a $==$ cksum$1$b && cksum$2$a $==$ cksum$2$b $?$

"success." : "FAILED"$)<<$ endl;

if $($verbose$)\{$

cout $<<$ endl $<<$ "After sort:" $<<$ endl;

print$($x$,$ size$)$;

cout $<<"$ Checksums: $"<<$ cksum$1$b $<<""<<$ cksum$2$b $<<$ endl $<<$ endl;

$\}$

cout $<<$ "Run time: $"<<$ fixed $<<$ setprecision$(2)<<$

$(($double$)$t$)/$ CLOCKS$\_$PER$\_$SEC $<<"$ seconds." $<<$ endl;

delete$[]$ x;

$\}$

int checksum$1($int a$[],$ int n$)\{$

int cksum $=0$;

for $($int i $=0$; i $<$ n; i$++)$

cksum $+=$ a$[$i$]$;

return cksum;

$\}$

int checksum$2($int a$[],$ int n$)\{$

int cksum $=0$;

for $($int i $=0$; i $<$ n; i$++)$

cksum $^=$ a$[$i$]$;

return cksum;

$\}$

void print$($int a$[],$ int n$)\{$

char fill $=$ cout.fill$()$;

cout $<<$ setfill$(\text{'}0\text{'})$;

for $($int i $=0$; i $<$ n; i$++)\{$

if $($i && $!($i $\%10))$

cout $<<$ endl;

cout $<<""<<$ setw$(5)<<$ a$[$i$]$;

$\}$

cout $<<$ endl $<<$ setfill$($fill$)$;

$\}$

bool is$\_$sorted$($int a$[],$ int n$)\{$

for $($int i $=0$; i $<$ n $-1$; i$++)$

if $($a$[$i$]>$ a$[$i $+1])$

return false;

return true;

$\}$