Question

23.8 (Generic insertion sort) Write the following two generic methods using insertion sort. The first method sorts the elements using the Comparable interface, and the second uses the Comparator interface.(Use Java program)
public static > void insertionSort(E[] list)

public static void insertionSort(E[] list, Comparator comparator)

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks

EDIT: created a class called IntegerComparator that implements Comparator interface and implemented compare() method. Inside main() of Test class, sorted the array using insertionSort method, passing an object of IntegerComparator as Comparator.

// Test.java

import java.util.Collections;

import java.util.Comparator;

public class Test {

      /**

      * required method to sort an array using natural order (based on compareTo

      * value defined in type E.) Since we need to use compareTo method, we have

      * to add constraints to the type parameter E to be subclasses of Comparable

      * interface. i.e only those objects that implement comparable interface can

      * be passed to this method

      *

      * @param array

      *            array to be sorted

      */

      public static <E extends Comparable<E>> void insertionSort(E[] array) {

            int i, j;

            E key;

            // looping from i=1 to i=n-1

            for (i = 1; i < array.length; i++) {

                  // taking element at index i as key value

                  key = array[i];

                  // previous index

                  j = i - 1;

                  // looping through each previous element, shifting each value

                  // greater than key to one place right. at any point if the key is

                  // smaller than or equal to any element, the inner loop will stop.

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

                        // storing element at j in j+1

                        array[j + 1] = array[j];

                        j--;

                  }

                  // now inserting key at proper position. after this line, the

                  // elements upto index i will be in sorted order.

                  array[j + 1] = key;

            }

      }

      /**

      * method to sort the array using a given comparator.

      *

      * @param array

      *            array to be sorted

      * @param comparator

      *            comparator to be used

      */

      public static <E> void insertionSort(E[] array, Comparator<E> comparator) {

            int i, j;

            E key;

            // looping from i=1 to i=n-1

            for (i = 1; i < array.length; i++) {

                  // taking element at index i as key value

                  key = array[i];

                  // previous index

                  j = i - 1;

                  // looping through each previous element, shifting each value

                  // greater than key to one place right. at any point if the key is

                  // smaller than or equal to any element, the inner loop will stop.

                  while (j >= 0 && comparator.compare(array[j], key) > 0) {

                        // storing element at j in j+1

                        array[j + 1] = array[j];

                        j--;

                  }

                  // now inserting key at proper position. after this line, the

                  // elements upto index i will be in sorted order.

                  array[j + 1] = key;

            }

      }

      // main method for testing the above method

      public static void main(String[] args) {

            // creating an array of integers

            Integer array[] = { 12, 22, -22, 76, 33, 8, 0, 1, 19, 7 };

            // printing array

            System.out.println("Array before sorting: ");

            for (int i = 0; i < array.length; i++) {

                  System.out.print(array[i] + " ");

            }

            System.out.println();

            // sorting the array using the first method we defined, in ascending

            // order (default order)

            insertionSort(array);

            // printing array again

            System.out.println("Array after sorting in ascending order: ");

            for (int i = 0; i < array.length; i++) {

                  System.out.print(array[i] + " ");

            }

            System.out.println();

            // creating an object of IntegerComparator

            IntegerComparator comparator=new IntegerComparator();

            // sorting the array using the second method we defined, using this

            // comparator

            insertionSort(array, comparator);

            // printing array again

            System.out

                        .println("Array after sorting in ascending order using comparator: ");

            for (int i = 0; i < array.length; i++) {

                  System.out.print(array[i] + " ");

            }

            System.out.println();

      }

}

//a class that implements Comparator interface to compare Integers

class IntegerComparator implements Comparator<Integer> {

      // returns a negative value if first<second, positive if first>second, 0 if

      // they are same

      public int compare(Integer first, Integer second) {

            return first - second;

      }

}

/*OUTPUT*/

Array before sorting:

12 22 -22 76 33 8 0 1 19 7

Array after sorting in ascending order:

-22 0 1 7 8 12 19 22 33 76

Array after sorting in ascending order using comparator:

-22 0 1 7 8 12 19 22 33 76