Question

Homework: Insertion Sort

Create a public class named InsertionSorter. It should provide one class method sort. sort accepts an array of Comparables and sorts them in ascending order. You should sort the array in place, meaning that you modify the original array, and return the number of swaps required to sort the array as an int. That's how we'll know that you've correctly implemented insertion sort. If the array is null you should throw an IllegalArgumentException. You can assume that the array does not contain any null values.
To receive credit implement insertion sort as follows. Have the sorted part start at the left and grow to the right. Each step takes the left-most value from the unsorted part of the array and move it leftward, swapping elements until it is in the correct place. Do not swap equal values. This will make your sort unstable and cause you to fail the test suites.

Answer 1

The InsertionSorter class implements the insertion sort algorithm in Java, with the sort method sorting a Comparable array in place and returning the number of swaps. The array should not be null, and equal values must not be swapped to maintain stability.

Step-by-step explanation:

The student is tasked with creating a public class named InsertionSorter that implements the insertion sort algorithm in Java. This class will have a class method sort which accepts an array of Comparable objects and sorts them in place in ascending order. The method should also return the number of swaps made during the sorting process as an integer. If the input array is null, the method should throw an IllegalArgumentException. Since we are sorting the array in place, we will be modifying the original array directly, without using additional memory for another array.

The insertion sort algorithm should work as follows: it will start with the first element of the array as the sorted part and incrementally take the next element from the unsorted part, moving it backwards through the sorted section until it finds its correct position. It's important to remember that the original problem statement specifies not to swap equal values; this ensures the stability of the sort and the correctness of the implementation with respect to the instructions provided. If two elements are equal, they should maintain their original order.

Answer 2

Step-by-step explanation:

I have written the code in Java. It contains the class Insertion Sorter which has the InsertionSort function. This function uses the insertion sort algorithm to sort a comparable array and if it fails to do so for whatever reason it throws an Illegal ArgumentException. If it sorts the array correctly it returns the number of changes that needed to be made in order to correctly sort the array. Due to technical difficulties I have attached the code as a text document below and proof of output in the picture below as well.