Explore BrainMass

Decision tree for the insertion sort algorithm

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

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.

// 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;

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;


© BrainMass Inc. brainmass.com October 25, 2018, 2:50 am ad1c9bdddf

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, ...

Solution Summary

The decision tree for the insertion sort algorithm is examined.

See Also This Related BrainMass Solution

Efficiency of algorithm finding the second smallest of n elements

Prove that the second smallest of n elements can be found with n + cieling(log n) - 2 comparisons in the worst case.

View Full Posting Details