Redo insertion sort to sort in nonincreasing order.

Question

What will be an ideal response?

Answer 1

```
Solution is below and also with the Instructor’s code.
The cost is the same as for the ascending order implementation.

/**
* Sort an array of integers in non-increasing order using insertion sort.
* @param a the array of integers to sort
* @throws NullPointerException if the array object is null
*/
public static void insertionSortNonIncreasing( int[] a ) {
int target; // the element we want to insert
int targetPos; // position of the first element of the unsorted section
int pos;

if ( a == null ) {
throw new NullPointerException();
}

// while the size of the unsorted section is greater than 0
// when targetPos reaches a.length, there are no more unsorted elements
for ( targetPos = 1; targetPos < a.length; targetPos++ ) {
// get a copy of the first element in the unsorted section
target = a[targetPos];

// while there are elements in the unsorted section to examine AND
// we haven't found the insertion point for target
for ( pos = targetPos - 1; ( pos >= 0 ) && ( a[pos] <= target ); pos-- ) {
// the element at pos is > target, so move it up in the array
a[pos + 1] = a[pos];
}
// loop postcondition: pos == -1 or a[pos] <= target,
// so pos + 1 is the new home for target

// insert target in its final sorted position
a[pos + 1] = target;
}
}

```