Modify the selection sort algorithm so it avoids the element move step if the element is already in the correct position. On what basis would you decide that the cost of this extra check outweighs the cost of not doing the check?

Question

What will be an ideal response?

Answer 1

```
Solution is below and also with the Instructor’s code.
You make the change based on the likelihood that the swap won’t actually move a data element. If the likelihood of this is small, doing the extra check for all the cases where data will be moved becomes expensive.

/**
* Sort an array of integers in ascending order using selection sort.
* @param a the array of integers to sort
* @throws NullPointerException if the array object is null
*/
public static void selectionSort( int[] a ) {
if ( a == null ) {
throw new NullPointerException();
}

// while the size of the unsorted section is > 1
for ( int unsortedSize = a.length; unsortedSize > 1; unsortedSize-- ) {
// find the position of the largest element in the unsorted part
int maxPos = 0;
for ( int pos = 1; pos < unsortedSize; pos++ ) {
if ( a[pos] > a[maxPos] ) {
maxPos = pos;
}
}
// postcondition: maxPos is the position of the largest element in
// the unsorted part

if ( maxPos != unsortedSize - 1 )
{
// Swap the largest value with the last value in the unsorted part
int temp = a[unsortedSize - 1];
a[unsortedSize - 1] = a[maxPos];
a[maxPos] = temp;
}
}
}

```