implementing comprable method in a generic way in Java for sorting

Question

I am trying to implement a generic selection sort which can take any objects and do the sorting on it. I can promise to the compiler that whatever objects I am comparing, has the compareTo method implemented for it. But I get compile error for the following code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class SelectionSortGenerics implements Comparable<E> {

    private <E> void swap(E[] a, int i, int j) {
        if (i != j) {
            E temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

    public <E> void selectionSort(E[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            // find index of smallest element
            int smallest = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j].compareTo(a[smallest])<=0) {
                    smallest = j;
                }
            }

            swap(a, i, smallest);  // swap smallest to front
        }
    }

    public static void main(String[] args){
        SelectionSortGenerics firstsort = new SelectionSortGenerics();

        Integer[] arr = {3,4,1,5};
        System.out.println("before sorting int: "+ Arrays.toString(arr));
        firstsort.selectionSort(arr);
        System.out.println("After sorting int : "+Arrays.toString(arr));
         String[] arr1= {"acd","ded","dal","bad","cle"};
         System.out.println("before sorting String: "+ Arrays.toString(arr1));
         firstsort.selectionSort(arr1);
         System.out.println("After sorting String : "+Arrays.toString(arr1));
         Character[] arr2= {'c','e','a','d','c'};
         System.out.println("before sorting char: "+ Arrays.toString(arr2));
         firstsort.selectionSort(arr2);
         System.out.println("After sorting char : "+Arrays.toString(arr2));
    }
}

As you can see, the objects I am passing in main method are Integer, String and Character, which has compareTo methods. how would make the above code work. Anywhere, casting is needed? Thanks for your help.

Answer 1

Note: The sorting algorithm implemented below works only for an array of the length of a power of two. You can use this technique for other sorting algorithms too:

Approach 1: Using java.util.Comparator

Approach 2:Using T extends Comparable

Main Method:Main method

Answer 2

 **Refer below method to implement generic sorting.You just have to pass list in sortElements    and  the name of the field on you want to enable sorting**
 /**
 * This method is used to sort the elements based on the fieldName specified.
 * Sorting order is Ascending order.
 * 
 * @param resultList
 *            e.g., List of ProductBrand
 * @param fieldName
 *            e.g., productBrandName list will be sorted according to this
 *            fieldName.
 * @throws Exception
 */
public static <Type> void sortElements(List<Type> resultList, final String fieldName, final boolean isDesc) throws Exception
{
  Collections. sort(resultList, new Comparator<Type>()
  {
          @Override
          public int compare(Type o1, Type o2)
         {
                return compareValue(o1, o2);
         }

          private int compareValue(Type o1, Type o2)
         {
                int returnValue = 0;
                try
               {
                      Field field = o1.getClass().getDeclaredField(fieldName);
                       boolean accessible = field.isAccessible();
                      field.setAccessible( true);
                      Object objectO1 = field.get(o1);
                      Object objectO2 = field.get(o2);
                       if (objectO1 instanceof Number)
                      {
                              if ((objectO1 != null && objectO2 != null)
                                           && (objectO1 instanceof Integer || objectO1 instanceof Long || objectO1 instanceof Byte))
                             {
                                    returnValue = Long.valueOf(objectO1 + "").compareTo(Long. valueOf(objectO2 + ""));
                             }
                              else if ((objectO1 != null && objectO2 != null) && (objectO1 instanceof Double || objectO1 instanceof Float))
                             {

                                    returnValue = Double.valueOf(objectO1 + "").compareTo(Double. valueOf(objectO2 + ""));

                             }
                      }
                       else if (objectO1 instanceof String || objectO1 instanceof Character)
                      {
                              if ((objectO1 != null) && objectO2 != null)
                             {
                                    returnValue = normalizedString(String.valueOf(objectO1)).compareToIgnoreCase(
                                                   normalizedString(String.valueOf(objectO2)));
                             }
                      }
                      field.setAccessible(accessible);
               }
                catch (Exception e)
               {
                      System. out.println("Error occured while sorting elements");
               }

                if (isDesc)
               {
                       if (returnValue > 0)
                      {
                              return -1;
                      }
                       else if (returnValue < 0)
                      {
                              return 1;
                      }
               }
                return returnValue;
         }
  });

}

 /**
 * This methods Normalizes the input string. Here we remove accent from the
 * character so that we can sort the string properly using normal characters.
 * 
 * @param str
 *            example <B> BSH Electrodom�sticos Espa�a S.A. </b>
 * @return Normalized String . <B> ex : BSH Electrodomesticos Espana S.A.</b>
 * 
 */
 public static String normalizedString(String str)
 {
   if (!isNullOrBlank(str))
  {
         String nfdNormalizedString = Normalizer. normalize(str, Normalizer.Form.NFD );
         Pattern pattern = Pattern.compile("\\p{InCombiningDiacriticalMarks}+");
          return pattern.matcher(nfdNormalizedString).replaceAll("");
  }
   else
  {
          return "" ;
  }
 }

 /**
 * This function checks that the value is blank or null.
 * 
 * @param value
 *            value to be checked
 * @return true if value is blank or null
 */
 public static boolean isNullOrBlank(String value)
 {
   boolean retFlag = false;
   if (value == null || value.trim().equals("") || value.trim().equals("null" ))
  {
         retFlag = true;
  }
   return retFlag;
 }

Answer 3

The following works for me. All I did was remove the <E> in the class declaration and changed <E> to <E extends Comparable<E>> in selectionSort.

The generic <E> in the class declaration is unnecessary and potentially confusing since your class doesn't actually need to be generic. Only the methods in the class are generic, not the class itself.

Second, the selectionSort method requires the element type passed in to be comparable to itself. You can represent this by E extends Comparable<E>.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class SelectionSortGenerics {

    private <E> void swap(E[] a, int i, int j) {
        if (i != j) {
            E temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

    public <E extends Comparable<E>> void selectionSort(E[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            // find index of smallest element
            int smallest = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j].compareTo(a[smallest])<=0) {
                    smallest = j;
                }
            }

            swap(a, i, smallest);  // swap smallest to front
        }
    }

    public static void main(String[] args){
        SelectionSortGenerics firstsort = new SelectionSortGenerics();

        Integer[] arr = {3,4,1,5};
        System.out.println("before sorting int: "+ Arrays.toString(arr));
        firstsort.selectionSort(arr);
        System.out.println("After sorting int : "+Arrays.toString(arr));
         String[] arr1= {"acd","ded","dal","bad","cle"};
         System.out.println("before sorting String: "+ Arrays.toString(arr1));
         firstsort.selectionSort(arr1);
         System.out.println("After sorting String : "+Arrays.toString(arr1));
         Character[] arr2= {'c','e','a','d','c'};
         System.out.println("before sorting char: "+ Arrays.toString(arr2));
         firstsort.selectionSort(arr2);
         System.out.println("After sorting char : "+Arrays.toString(arr2));
    }
}