can you help me answer the short questions by looking at the code provided below?

Type your answers here

Would you use Selection Sort or would you use Insertion Sort?

Why?

Rika-Chu Sort corrects one inversion per comparison.

What is its worst case number of comparisons?

Why?

What is the advantage of using Merge Sort over Quick Sort?

What is the disadvantage of using Merge Sort over Quick Sort?

Why is Radix sort unrelated to the F(n) = O(nlogn) theorem?

B) Sort

230 123 324 10 23 56 (6 items)

using Insertion Sort and fill in the answers below.

[1/2 per prompt=7pts] Your score:

Start with pos 2 for X index:

Which items were shifted?

How many element comparisons until X is deposited back?

The resulting list is?

Start with pos 3 for X index:

Which items were shifted?

How many comparisons until X is deposited back?

The resulting list is?

Start with pos 4 for X index:

Which items were shifted?

How many comparisons until X is deposited back?

The resulting list is?

Start with pos 5 for X index:

Which items were shifted?

How many comparisons until X is deposited back?

The resulting list is?

Start with pos 6 for X index:

Which items were shifted?

How many comparisons until X is deposited back?

The final resulting sorted list is?

Q) Total number of comparisons was (add up the above):

Q) Give an example list for which you would have made the worst number of comparisons:

C) Using the Merge Sort algorithm, sort [1/4 per prompt=9pts] Your score:

8 5 6 3 9 2 1 7.

Fill in the []s:

Break this up into: [] and []

Break these up into: [] and [] [] and []

Further Break these up into: [] and [] [] and [] [] and [] [] and []

For the one element lists (left to right):

Combine what and what?

Produce what?

How many element comparisons for this part?

Combine what and what?

Produce what?

How many comparisons for this part?

Combine what and what?

Produce what?

How many comparisons?

Combine what and what?

Produce what?

How many comparisons?

For the two element lists (left to right):

Combine what and what?

Produce what?

How many comparisons?

Combine what and what?

Produce what?

How many comparisons?

Final step:

Combine what and what?

Produce what? (the final result):

How many comparisons?

Q) Total number of comparisons was? (add up the above):

D) Sort

231 123 324 100 230 560 (6 items)

using Radix Sort.

Hint: list 0-list, 1-list, 3-list, 4-list etc. [1 per prompt=6pts] Your score:

Pass1:

Show the sub-lists here based on the last char

Show the combined list

Pass2:

Show the sub-lists here based on the second char

Show the combined list

Pass3:

Show the sub-lists here based on the first char

Show the combined list

//=========================================================

//HW#: HW2P2 Combine

//Your name: Stefan Retief

//Complier: g++/XCode

//File type: client program/combine merge sort

//===========================================================

#include

#include

using namespace std;

void combine(vector, vector, vector&); //prototype for our combine func

//PURPOSE: To ask the user to input lists that will be sorted using merge sort.

//ALGORITHM: Create 3 vectors that will recieve the elements. Ask the user to input

// how many numbers will inputted into each list. We will resize a third

// vector to recieve the right size of elements by multiplying the amt by

// 2. Then we will send the list to combine, and return the result.

int main() {

vector L1; //init our 3 vectors that will hold our values

vector L2; //lists 1 & 2 will be inputted by the user

vector L3; //list 3 will be the result of merge sort and combine

int amt; //the amount of elements in each list

int elm; //the element from the user

cout << "How many elements do you want? :"; //ask the user for how many

cin >> amt; //take the value from the user

cout << "** List 1 **" << endl; //now we will make the first list

for (int i = 1; i <= amt; i++) { //keep adding elements until we have

cout << "Element " << i << ": "; //the right amount of elements

cin >> elm;

L1.push_back(elm); //add each input to the vector

}

cout << " ** List 2 **" << endl; //now we'll start list 2

for (int i = 1; i <= amt; i++) { //again, keep adding until we have enough

cout << "Element " << i << ": ";

cin >> elm;

L2.push_back(elm); //add each element to the vector

}

L3.resize(2 * amt); //we need to make the result vector the right size,

//or we will run into an err

combine(L1, L2, L3); //combine the lists and get the third list back by ref

cout << " R: "; //display the third list after combining

for (int i = 0; i < L3.size(); i++) { //we want to display each element

cout << L3[i] << " ";

}

cout << endl;

}

// PURPOSE: To combine the 2 lists into one while merge sorting.

// PARAMETERS: Pass the two lists we recieved from the user by value, and the list that will

// recieve the combined list by reference.

// ALGORITHM: Recieve the 3 list and compare the elements of each list to create a larger

// correctly oredered list. return the third list by reference.

void combine(vector A, vector B, vector& R) // combine sorted lists A and B

{

int ia = 0; // index for A

int ib = 0; // index for B

int ir = 0; // index for R

while (ia < A.size() && ib < B.size()) {//Until you run out of elements in A

//or run out of elements in B

if (A[ia] < B[ib]) {

R[ir] = A[ia];

ia++; // get the A element

}

else {

R[ir] = B[ib];

ib++; // get the B element

}

cout << " Comparison"; //we need to show when we make a comparison

ir++;

}

if (ia < A.size()) { //you still have A elements left, copy them into R

cout << " The rest of the first one goes down.";

for (; ia < A.size(); ia++, ir++) {

R[ir] = A[ia];

}

}

else { //copy the remaining B elements into R.

cout << " The rest of the second one goes down.";

for (; ib < B.size(); ib++, ir++) {

R[ir] = B[ib];

}

cin.get();

}

}