Question 3 In this question you will measure the performance of selection sort a

Question

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 and swaps needed to sort a randomly generated array of N doubles.

Write (static) methods:

boolean isSorted(double[] a) – returns true if and only if the array a is sorted.

double[] random(int N) – returns an array of doubles of size N where each entry in the array is a random double between 0 and 1 (use Math.random()).

void selection(double[] a) – sorts the array a using selection sort.

void insertion(double[] a) – sorts the array a using insertion sort.

Instrument your two sorting routines to count the number of compares and swaps each routine does. Write a main method which, for various appropriate choices of N:

generates 100 random arrays of size N, calls selection sort on each, checks that each 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 each array is sorted, and outputs the average number of compares per call.

You main method should use your isSorted() method to check that each array is sorted after you have run your sort method.

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, 12 N2 and 14 N2, all on the same axis.

Remark:

Be careful not to 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!

Explanation / Answer

First of all, one should ask why use a quadratic sorting algorithm when asymptotically faster alternatives exists, like mergesort or quicksort. For small arrays (less than 20-30 elements), both insertion sort and selection sort are typically faster than the O(n*logn) alternatives. In fact, many sorting algorithms based on the divide and conquer paradigm switch to insertion sort or selection sort when the array is small enough.

Between insertion sort and selection sort, when to use which?

Usually, insertion sort will perform less comparisons than selection sort, depending on the degree of "sortedness" of the array. While selection sort must scan the remaining parts of the array when placing an element, insertion sort only scans as many elements as necessary. That means that when the array is already sorted or almost sorted, insertion sort performs in O(n) time.

One advantage of selection sort against insertion sort, is that the number of writes (swaps) is in O(n), while in insertion sort it is in O(n^2). This may be important if you are sorting on Flash memory, for example, because writes reduce the lifespan of Flash memory.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.