HW2 Part 2 – Sorting Analysis (based on week4 - week 5) solution

Purpose: To demonstrate your understanding of analyzing searching and sorting algorithms.

------------------------------------------------------------------------------------------

A)
Review Questions [1pt per question = 5pts]
Your score is:
Type your answers here







Would you use Selection Sort or would you use Insertion Sort? Insertion sort
•Why?










Rika-Chu Sort corrects one inversion per comparison.



What is its worst case number of comparisons?



The worst case sceanario or W(n) of Rika-Chu sort would be (n-1)/2

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?



Radix sort is unrelated to F(n) = O(nlogn) theorem because it does not use comparisions.

B) Sort




230 123 324 10 23 56
(6 items)
using Insertion Sort and fill in the answers below.








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







Start with pos 2 for X index:




Which items were shifted?




How many element comparisons until X is deposited back?

1

The resulting list is?







Start with pos 3 for X index:




Which items were shifted?




How many comparisons until X is deposited back?







Start with pos 4 for X index:




Which items were shifted?




How many comparisons until X is deposited back?

3

The resulting list is?




Start with pos 5 for X index:




How many comparisons until X is deposited back?

4

The resulting list is?




Start with pos 6 for X index:




Which items were shifted?




How many comparisons until X is deposited back?

4

The final resulting sorted list is?




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




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

324 230 123 56 23 10




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:








1.
Break this up into:
[8 5 6 3] and [9 2 1 7]




2.
Break these up into:
[8 5 ] and [6 3]
[9 2]


and [1 7]








3.


Further Break these up into:
[8] and [5] [6] and [3] [9] and [2] [1] and
[2]





















For the one element lists:




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:




Combine what and what?




Produce what?




How many comparisons? 3




Combine what and what?







Produce what?




How many comparisons? 3




Final step:




Combine what and what?







How many comparisons? 7




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







D) Sort







using Radix Sort.

Hint: use 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




100 230 560 231 123 324

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










E) Program Merge Sort’s Combine: [2+8=10 pts] Your score:







Using Notes-4B.doc, code only the Procedure Combine of Merge Sort. No ADT is needed. Just one source code file. – Run my solution program first.




Void Combine will take 3 vectors as arguments: A, B and R.




Combine should work for any size vectors as long as the size of A and B are the same.

It will combine the elements of A and B into R to produce the sorted list R.

You should know how to find the size of a vector.

Display “comparison” every time an element-element comparison is done.




Your main()




Will declare three vectors L1, L2 and L3.
Will ask the user to type integers in increasing order into L1.
Then ask the user to type more integers in increasing order into L2.
Then it will call void Combine to combine L1 and L2 to produce L3 which is passed back by reference.
Display what is in L3.



Required Test Cases: (Must test in this order)




Combine 1 2 3 with 4 5 6
Combine 1 3 5 with 2 4 6
Combine 4 5 6 with 1 2 3
Combine 1 2 5 6 with 3 4 7 8






Q) State of the program [2pts]




Does your program compile without errors? If not, describe: yes



List any bugs you are aware of, or state “No bugs”: no bugs



Submit these 3 files:




This assignment sheet with inserted answers.
Source code file (combine.cpp) of the program (with good comments).
Script (Test) of the compilation and test results.
Did you answer all the questions?