## Question

Choose one of the questions below (at your own convenience – don’t be overwhelmed by the large number of alternatives; choose just one!

1. Stability represents the property of an algorithm to preserve the relative order of equal elements (that is, in case 2 or several elements have the same key, they will occur in the same order in the output as in the input). Stability is an important property, which is often required. For either Selection Sort or Insertion Sort identify if it is stable. If it is, try to show (informal is OK). If it is not, identify the issue(s), and specify the change(s) required to make it stable.

2. Selection Sort has for (i = 0; i < array.length; i++) as outer loop. Is it possible to change it to for (i = 0; i < array.length-1; i++). Why/why not. Justify your answer and give an example.

3. Considering the Selection Sort algorithm efficiency: how is it affected by the choice of storing the index of the minimum element in the array (minIndex) rather than the element itself? Justify your statement.

4. Can the Selection Sort algorithm be improved? How? Which operations (comparisons or/and assignments) are improved? In all cases?

5. For Insertion Sort in the inner loop why j starts at i-1 and not i?

6. Is it possible to avoid the compound condition (while (j >= 0 && temp.compareTo(array[j]) < 0) in the inner loop for Insertion Sort? How?

Draw a diagram similar to the one in Figure 1.V.1 – Graph of T(N) compared to that of 5N2 (from Mathematics Review, Preliminaries and Simple Data Structures topic) for at least 3 functions and n in the range [1, 1000]. For doing this use xls(x) spreadsheet.

Part II

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

Approach: For doing this, you should evaluate their corresponding implementations (their code is:

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);

}

}

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;

}

}

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.

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)).

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).

Deliverables: You should submit (1) all the source (.java) files, (2) an output sample (screenshot showing program execution and the results of your testing, to show the methods are actually sorting) (3) the diagrams (the easiest way to draw them is by using Microsoft Excel Worksheet) and (4) a document file describing your solution. The solution description document should include the following elements: justification for the added statements (to ones that increment the counters), interpretation of the diagrams and lessons learned. The size of the document should be of 1-2 pages, single spaced, font size 12. All solution description elements should be properly formatted using APA style.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

Part I1.

We shouldn’t do this

Because the new condition ignores the last item in the array

It won’t be sorted

Example

We have this array

{5,6,8,1,4,5,6}

If we use the first condition, we will get this result

{1,4,5,5,6,6,8}

If we use the second condition, we will get this result

{1,4,5,5,6,8,6}...