#include

using namespace std;

$//$ Let's get started. Given an array of strings, swap the positions of

$//$ the elements at idx$1$ and idx$2$

$//$ For example, if names contains $\{"$A$","$B$","$C$","$D$","$E$"\}$ and we call

$//$ swap$($names$,1,3)$ names will contain $\{"$A$","$D$","$C$","$B$","$E$"\}$ on output,

$//$ swapping element $1"$B$"$ with element $3"$D$"$

void swap$($string names$[],$ int idx$1,$ int idx$2)\{$

$\}$

$//$ This one is a bit more complex but read this carefully to get an unsterstanding of what it does...

$//$ names is a partially sorted array of strings

$//$ itemIndexToInsert is the index of the first item in the array that HAS NOT been sorted yet.

$//$ For example, on input names may contain $\{"$A$","$C$","$B$","$E$","$D$"\}$ and itemIndexToInsert is $2$

$//$ This means that items $0$ and $1$ have been sorted and item $2("$B$")$ is the first item that has not been

$//$ sorted it$.$

$//$ The job of this function is to move the element at the index itemIndexToInsert into the sub$-$list

$//$ that is immediately before it in the array.

$//$ In our example we need to move the $"$B$"$ into the proper position in the sub$-$list $"$A$","$C$"$

$//$

$//$ The algorithm:

$//$ loop from itemIndexToInsert backwards $($count down to $0$ instead of up in the loop$)$

$//$ compare the element at itemIndexToInsert with the previous element in the list $($itemIndexToInsert$-1)$

$//$ if the they are out of order...

$//$ swap them $($call your swap function$)$

$//$ decrease itemIndexToInsert by $1$

$//$ else

$//$ things are in order so stop your loop

$//$

void insertItemFromIndex$($string names$[],$ int itemIndexToInsert$)\{$

$//$ loop from itemIndexToInsert backwards $($count down to $0$ instead of up in the loop$)$

$//$ compare the element at itemIndexToInsert with the previous element in the list $($itemIndexToInsert$-1)$

$//$ if the they are out of order...

$//$ swap them $($call your swap function$)$

$//$ decrease itemIndexToInsert by $1$

$//$ else

$//$ things are in order so stop your loop

$\}$

$//$ Given an array of strings and the size, use insertion sort to put the elements into ascending

$//$ alphabetical order.

$//$ Start by assuming that the first element is already sorted, so we can loop from index $1($skip the first element$)$

$//$ Loop on all of the unsorted elements $($from the $2$nd to the last$)$

$//$ call the insertItemFromIndex function, passing the array and the index of the current element to insert

void insertionSort$($string names$[],$ int size$)\{$

$//$ Loop on all of the unsorted elements $($from the $2$nd to the last$)$

$//$ call the insertItemFromIndex function, passing the array and the index of the current element to insert

$\}$

$//$ Print out the array with a comma and space between each element.

$//$ I wrote this one for you but if you want to try it yourself, feel free to

$//$ delete the code and rewrite it$!$ ;$)$

void printArray$($string names$[],$ int size$)\{$

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

cout $<<$ names$[$i$]$;

if $($i $<$ size$-1)$ cout $<<","$;

$\}$

cout $<<$ endl;

$\}$

$//$ Code to test your functions...

int main$()$

$\{$

string swapTest$[]=\{"$A$","$B$","$C$","$D$"\}$;

cout $<<$ "Testing swap. Before swapping:

$"$;

printArray$($swapTest$,4)$;

cout $<<$ "Swapping element $0$ and $2$

$"$;

swap$($swapTest$,0,2)$;

printArray$($swapTest$,4)$;

cout $<<$ "Swapping element $2$ and $0$

$"$;

swap$($swapTest$,2,0)$;

printArray$($swapTest$,4)$;

cout $<<$ "Swapping element $1$ and $3$

$"$;

swap$($swapTest$,1,3)$;

printArray$($swapTest$,4)$;

string insertTest$[]=\{"$A$","$C$","$D$","$B$"\}$;

cout $<<$ "Testing insertItemFromIndex. Before insertItemFromIndex:

$"$;

printArray$($insertTest$,4)$;

cout $<<$ "Inserting element $3.$ Expect B to be moved between A and C

$"$;

insertItemFromIndex$($insertTest$,3)$;

printArray$($insertTest$,4)$;

string names$[]=\{$

"Twenty One Pilots",

"The Beatles",

"Pink Floyd",

$"$AC$/$DC$",$

"Metallica",

"Nirvana",

"Arctic Monkeys",

"Imagine Dragons",

"The Black Keys",

"Tame Impala" $\}$;

cout $<<$ "Testing sort. Before sorting:

$"$;

printArray$($names$,10)$;

insertionSort$($names$,10)$;

cout $<<$ "After Sorting:

$"$;

printArray$($names$,10)$;

return $0$;

$\}$