Question

USE GENERICS TO WRITE THE JAVA CODE FOR THIS ASSIGNMENT

In this assignment, rewrite two of the following sorting methods (Insertion Sort, Selection Sort, Quick Sort, and Merge Sort) to sort ArrayList of objects using Comaprable interface. (60 points)

Answer 1

// Java program to create methods for sorting generic arraylist data

import java.util.ArrayList;
import java.util.Random;
public class GenericSorting {
  
   // generic method that partitions the given arraylist and returns the location of the pivot
   public static <T extends Comparable<T>> int partition(ArrayList<T> data,int low, int high)
   {
       int mid = (low+high)/2; // mid element is selected as the pivot
       swap(data,low,mid);
       int pivotkey = low;
       T pivot = data.get(low);
       for(int i=low+1;i<=high;i++)
       {
           if(data.get(i).compareTo(pivot) < 0)
               swap(data,i,++pivotkey);
       }
       swap(data,low,pivotkey);
       return pivotkey;
   }
  
   // generic method to implement quicksort on the given arraylist
   public static <T extends Comparable<T>> void quickSort(ArrayList<T> data,int low,int high)
   {
       int pivotkey;
       if(low<high)
       {
           pivotkey = partition(data,low,high);
           quickSort(data,low,pivotkey-1);
           quickSort(data,pivotkey+1,high);
       }
   }
  
   // generic method to swap the values at index1 and index2 of data arraylist
   public static <T> void swap(ArrayList<T> data, int index1, int index2) {
T temp = data.get(index1);
data.set(index1, data.get(index2));
data.set(index2,temp);
}
  
  
   // generic method to sort a given arraylist using mergesort
   public static <T extends Comparable<T>> void mergeSort(ArrayList<T> arr,int low,int high)
   {
       int mid;
       if(low<high)
       {  
          
           mid = (low+high)/2;
           mergeSort(arr,low,mid);
           mergeSort(arr,mid+1,high);
           mergeArr(arr,low,high,mid);
       }
   }
  
   // generic method to merge with sorted arraylist
   public static <T extends Comparable<T>> void mergeArr(ArrayList<T> arr,int low,int high,int mid)
   {
       int l = low;
       int h = mid+1;
       int i=low;
       T brr[] = (T[])new Comparable[arr.size()];      
       while(l<=mid && h<=high)
       {
           if(arr.get(l).compareTo(arr.get(h)) < 0)
           {
               brr[i] = arr.get(l);
               l++;
           }else
           {
               brr[i]=arr.get(h);
               h++;
           }
           i++;
       }
      
       while(l<=mid)
       {
           brr[i] = arr.get(l);
           i++;
           l++;
       }
      
       while(h<=high)
       {
           brr[i] = arr.get(h);
           i++;
           h++;
       }
  
       for(i=low;i<=high;i++)
       {
           arr.set(i, brr[i]);
       }
      
   }
  
   // generic method to sort a given arraylist using selection sort
   public static <T extends Comparable<T>> void selectionSort(ArrayList<T> arr)
   {
       int minIndex;
       for(int i=0;i<arr.size()-1;i++)
       {
           minIndex = i;
           for(int j=i+1;j<arr.size();j++)
           {
               if(arr.get(j).compareTo(arr.get(minIndex)) < 0)
                   minIndex = j;
           }
          
           if(i != minIndex)
           {
               T temp = arr.get(minIndex);
               arr.set(minIndex, arr.get(i));
               arr.set(i, temp);
           }
       }
   }
  
   // generic method to sort a given arraylist using insertionsort
   public static <T extends Comparable<T>> void insertionSort(ArrayList<T> arr)
   {
       int i,j;
       T key;
       for(i=1;i<arr.size();i++)
       {
           j=i-1;
           key = arr.get(i);
          
           while((j >=0) && (arr.get(j).compareTo(key) > 0) )
           {
               arr.set(j+1, arr.get(j));
               j--;
           }
          
           arr.set(j+1, key);
       }
   }
  
   public static void main(String[] args) {
       // test the quick sort, merge sort, selection sort and insertion sort methods
       ArrayList<Integer> quickData, mergeData, selectionData, insertData;
       quickData = new ArrayList<Integer>();
       mergeData = new ArrayList<Integer>();
       selectionData = new ArrayList<Integer>();
       insertData = new ArrayList<Integer>();
      
       Random ran = new Random();
       for(int i=0;i<10;i++)
       {
           int n = ran.nextInt(100);
           quickData.add(n);
           mergeData.add(n);
           selectionData.add(n);
           insertData.add(n);
       }
      
       System.out.println("Quick Sort Testing: ");
       System.out.println("Before : "+quickData.toString());
       quickSort(quickData,0,quickData.size()-1);
       System.out.println("After : "+quickData.toString());
      
      
       System.out.println("Merge Sort Testing: ");
       System.out.println("Before : "+mergeData.toString());
       mergeSort(mergeData,0,mergeData.size()-1);
       System.out.println("After : "+mergeData.toString());
      
       System.out.println("Insertion Sort Testing: ");
       System.out.println("Before : "+insertData.toString());
       insertionSort(insertData);
       System.out.println("After : "+insertData.toString());
      
       System.out.println("Selection Sort Testing: ");
       System.out.println("Before : "+selectionData.toString());
       selectionSort(selectionData);
       System.out.println("After : "+selectionData.toString());
   }
}
//end of program

Output: