Question

Create a public non-final class called InsertionSorter. It should provide one public class method called sort. Sort should accept an array of Comparable Java objects and sort them in ascending order. However, it should sort the array in place, meaning that you modify the original array, and return the number of swaps required to sort the array. That’s how we’ll know you’ve correctly implemented insertion sort. If the array is null or empty you should return 0. You can assume that the array does not contain any null values.

Answer 1

See explaination

Step-by-step explanation:

public class InsertionSorter {

/* Function to sort array using insertion sort */

int sort(Comparable arr[]) {

int count = 0;

if (arr == null || arr.length == 0)

return 0;

int n = arr.length;

for (int i = 1; i < n; ++i) {

Comparable key = arr[i];

int j = i - 1;

while (j >= 0 && arr[j].compareTo(key) > 0) {

count++;

arr[j + 1] = arr[j];

j = j - 1;

}

arr[j + 1] = key;

}

return count;

}

// Driver method

public static void main(String args[]) {

Integer arr[] = { 50,21,34,26, 18, 31, 37, 54 };

InsertionSorter ob = new InsertionSorter();

int comp = ob.sort(arr);

System.out.println("Comparisons required : "+comp);

for(int i:arr)

System.out.print(i+" ");

}

}