Jeremy - 4 months ago 41

Java Question

`public class Sorting`

{

public static int numOfComps = 0,

numOfSwaps = 0;

public static void insertionSort(int[] array)

{

int unsortedValue; // The first unsorted value

int scan; // Used to scan the array

// The outer loop steps the index variable through

// each subscript in the array, starting at 1. The portion of

// the array containing element 0 by itself is already sorted.

for (int index = 1; index < array.length; index++)

{

// The first element outside the sorted portion is

// array[index]. Store the value of this element

// in unsortedValue.

unsortedValue = array[index];

// Start scan at the subscript of the first element

// outside the sorted part.

scan = index;

// Move the first element in the still unsorted part

// into its proper position within the sorted part.

while (scan > 0 && array[scan-1] > unsortedValue)

{

array[scan] = array[scan - 1];

scan--;

// Counts the number of values swaps

numOfSwaps ++;

}

// Insert the unsorted value in its proper position

// within the sorted subset.

array[scan] = unsortedValue;

// Counts the number of values comparisons

numOfComps ++;

}

System.out.println("\n\nNumber of comps = " + numOfComps);

System.out.println("Number of swaps = " + numOfSwaps);

}

}

Newbie here again. How do I code this insertion sort program in Java to count the number of comparisons and the number of swaps? I have inserted comparison and swap codes into the program but not sure they're in the correct place. I have posted the program. Thanks for any help.

Answer

The number of comparisons is the number of times `array[scan-1] > unsortedValue`

is executed. That's not what you are counting.

Tips:

`while (EXPRESSION) { STATEMENTS }`

can be rewritten as`while (true) { if (!(EXPRESSION)) { break; } STATEMENTS }`

`!(EXPRESSION1 && EXPRESSION2)`

can be rewritten as`!(EXPRESSION1) || !(EXPRESSION2)`

.`if (EXPRESSION1 || EXPRESSION2) { break; }`

can be rewritten as`if (EXPRESSION1) { break; } if (EXPRESSION2) { break; }`

.

The algorithm doesn't swap the value of pairs of variables. However, there is a form of multi-variable swap that occurs (A⇒B, B⇒C, C⇒D, D⇒A). The number of times this occurs is the number of times `array[scan] = unsortedValue`

is executed when `scan`

is different than `index`

. That's not what you are counting.

Notes:

Your code is buggy.

`scan`

can be`-1`

when you reach`array[scan] = unsortedValue;`

. This will happen when sorting`2, 1`

.Note that this is a poor implementation of insertion sort. A binary search should be used instead of a linear search. This will reduce the maximum number of comparisons from N * N to N * log N.