Notes:
Include counts of compares and swaps in all trace tables for each row, and a total count when
done.
Do all trace tables by hand (don't write programs to generate them â€“ you will learn more).
Question 1
Do a trace table for selection sort for the following array of numbers: 15 12 16 13 11 14 10 17.
Do a trace table for selection sort for the following array of numbers: 10 11 12 13 14 15 16 17. What does this say about best case performance of selection sort?
Do a trace table for selection sort for the following array of numbers: 17 16 15 14 13 12 11 10. What does this say about worst case performance of selection sort?
Question 2
Do a trace table for insertion sort for the following array of numbers: 15 12 16 13 11 14 10 17.
Do a trace table for insertion sort for the following array of numbers: 10 11 12 13 14 15 16 17. What does this say about best case performance of insertion sort?
Do a trace table for insertion sort for the following array of numbers: 17 16 15 14 13 12 11 10. What does this say about worst case performance of insertion sort?
Question 3
In this question you will measure the performance of selection sort and insertion sort by plotting N against the average number of operations (comparisons plus swaps) needed to sort a randomly generated array of N doubles.
Write methods that:
return true if and only if an array of doubles is sorted.
generates a random array of doubles of size N from a random source R.
sorts an array of doubles using selection sort.
sorts an array of doubles using insertion sort.
Instrument your two sorting routines to count the total number of operations (comparisons plus
swaps) each routine does.
Write a main routine which, for various appropriate choices of N:
generates 100 random arrays of size N, calls selection sort on each, checks that the array is
sorted, and outputs the average number of operations per call.
generates 100 random arrays of size N, calls insertion sort on each, checks that the array is sorted, and outputs the average number of operations per call.
Do a plot (in Excel, OpenOffice, etc) of N against the number of operations (plot both sorts on the same plot), labeling the axis nicely, etc. Also plot N2, 1â„2 N2 and 1â„4 N2, all on the same axis.
Remark:
Be careful not to call sort on an already sorted array (doing so means you are measuring the worst/best case, and not the average case).
Strictly speaking you don't need to generate 100 arrays and average for selection sort since its best case, worst case and average case all the same.
Make sure your sorting and instrumentation code is correct before you start measuring the counts and doing the plots!
Question 4
Do a trace tree (as I did in class) for merge sort for the following array of numbers: 15 12 16 13 11 14
10 17 2.
Clearly indicate the order in which the merge sort and merge steps are done, and the result of each step.
Â
Question 5
In this question you will measure the performance of merge sort by plotting N against the number of
operations (comparisons plus copies) needed to sort a randomly generated array of N doubles. Write methods that:
takes two sorted array, A and B, and returns the merge of them.
sorts an array of doubles, A, using merge sort.
Instrument your sorting routine to count the number of operations (compares plus copies) done to merge sort an array of size N.
Write a main routine which, for various appropriate choices of N generates a random array of size N, calls merge sort on that array, checks that the array is sorted, and outputs the number of operations per N.
You should be able to sort for much larger values of N than in the previous assignment.
Do a plot (in Excel, OpenOffice, etc) of N against the number of operations, labeling the axis nicely,
etc. Also plot N log(N), 2N log(N), and 4N log(N), all on the same axis. NOTE: make sure you do base 2 logarithms, not base 10!Â
Subject | Computer |
Due By (Pacific Time) | 09/29/2015 06:00 pm |
Tutor | Rating |
---|---|
pallavi Chat Now! |
out of 1971 reviews More.. |
amosmm Chat Now! |
out of 766 reviews More.. |
PhyzKyd Chat Now! |
out of 1164 reviews More.. |
rajdeep77 Chat Now! |
out of 721 reviews More.. |
sctys Chat Now! |
out of 1600 reviews More.. |
sharadgreen Chat Now! |
out of 770 reviews More.. |
topnotcher Chat Now! |
out of 766 reviews More.. |
XXXIAO Chat Now! |
out of 680 reviews More.. |