Assignment

Requirements: Compare the efficiency of Selection Sort and Insertion Sort.

Approach: Evaluate the following Selection Sort and Insertion Sort codes in at least one case (best, worst, or average) and count the number of type of operations performed (assignments, comparisons, and overall, separately). For counting them, you need to add in the right place specific statements to increment the counters for assignments and/or comparisons, wherever needed.

Selection Sort code:

// Method: selectionSort
// Author: instructorX
// Date: dd/mm/yyyy
// Purpose: A method that sorts an array using a selection sort

public static void selectionSort(Comparable[] array)
{
int i;
for (i = 0; i < array.length; i++)
{
int minIndex = i;
for (int j = i + 1; j < array.length; j++)
if (array[j].compareTo(array[minIndex]) < 0)
minIndex = j;
swap(array, minIndex, i);
}
}

Insertion Sort code:

// Method: insertionSort
// Author: instructorX
// Date: dd/mm/yyyy
// Purpose: A method that sorts an array using an insertion sort

public static void insertionSort(Comparable[] array)
{
for (int i = 1; i < array.length; i++)
{
Comparable temp = array[i];
int j = i - 1;
while (j >= 0 && temp.compareTo(array[j]) < 0)
{
array[j + 1] = array[j];
j--;
}
array[j +1 ] = temp;
}
}

Draw charts to show how the running time (estimated in numbers of assignments A(n), comparisons C(n), and overall time T(n)=A(n) + C(n)) grows as the size of the input data n is growing. To draw the charts, vary the input size (n) between 100 and 1000, with an increment of maximum 100. For each size, generate the appropriate input sequence (best, worst, or average) for the specific sorting method (be aware: best/worst cases are not necessary the same for the two methods), run it, and store the values (A(n), C(n), T(n)). The easiest way to draw them is by using Microsoft Excel Worksheet.

In case the average case is your choice, you have to repeat the measurements m times (m=5 should suffice) and report their average. Moreover, for the average case, make sure you always use the same input sequence for both sorting methods for a fair comparison.

For the analyzed case(s), generate charts which compare the two methods; use different charts for the number of comparisons, number of assignments and total number of operations. Name your charts and curves on each chart appropriately (that is, specify what the chart/curve represents).