swap, and selection sort and insertion sort on Java

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 comparisons 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 (re-use your code from assignment 1) 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 number of compares 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 compares 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 compares per call. Do a plot (in Excel, OpenOffice, etc) of N against the number of compares (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!