Project #84051 - eclipse

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:

page1image15008 page1image15168 page1image15328 page1image15488
  • 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.

page2image16688

 

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
Report DMCA
TutorRating
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..
All Rights Reserved. Copyright by AceMyHW.com - Copyright Policy