Decision tree for the insertion sort algorithm

Question

Question:

Decision tree for the insertion sort algorithm

1. Draw the decision tree for the insertion sort algorithm for the following array of names: [Mickey, Minnie, Donald, Goofy].

2. Create a program to implement the selection sort algorithm, which will sort a list of strings. Selection sort function should sort the list of strings in alphabetical order. You only need to provide the details for the selectionSort() function based on the given framework.

#include < iostream >
#include < string >
#include < stdlib.h >

using namespace std;
void selectionSort(string items[], int numberOfItems)
{
//
// Hints:
// (1) You will need two for loops.
//
// (2) Use the strcmp() function in your if-statement
// to determine when one string is less than another.
// You will need to call this function with the c_str()
// method. For example:
// strcmp(items[i].c_str(), items[j].c_str());
//
// (3) You will need a temporary string when swapping
// the two strings.
//
return;
}

// Print the items in the list.
void printItems(string items[], int numberOfItems)
{
for (int i=0; i < numberOfItems; i++)
{
cout << items[i] << endl;
}
cout << endl;
return;
}

int main(int argc, char **argv)
{
string starTrekCharacters[] = {
"Picard", "Riker", "Data", "La Forge", "Worf", "Dr. Crusher",
"Dr. Pulaski", "Wesley", "Troi", "Tasha", "Sisko", "Odo",
"Dax", "O'Brien", "Quark", "Dr. Bashier", "Kira", "B'Elanna",
"Chakotay", "Janeway", "Neelix", "Seven of Nine", "Tuvok",
"Doctor", "Harry", "Tom", "Kes", "Archer", "T'Pol", "Tucker",
"Reed", "Travis", "Hoshi", "Dr. Phlox", "Kirk", "Spock",
"Bones", "Scotty", "Chekov", "Uhura", "Sulu", "Nurse Chapel"
};

int numberOfCharacters = 41;

// Print the unsorted items

cout << "Items unsorted:" << endl;

printItems(starTrekCharacters, numberOfCharacters);

// Sort the items

selectionSort(starTrekCharacters, numberOfCharacters);

// Print the sorted items

cout << "Items sorted:" << endl;

printItems(starTrekCharacters, numberOfCharacters);

return 0;

}

Solution Preview

Please see the attached document for #1.

For #2:

You need to add the following includes:

#include < iostream >
#include < cstdio >
#include < cstdlib >

Also, ...