Question

Exercice 3(25+ 20 pts); Sorting 1-Sorting is a classic subject in computer science. There are many sorting algorithms a. Complete the below code b.Add comments to the below code to explain each statement c. Write a main test then give the output screen of it 2- a-Write the following two generic methods using the below code. The first method sorts the elements using the Comparable interface and the second uses the Comparator interface. public static <E extends Comparable<E>> void Sort(E] list) public static <E> void Sort(E[] list,Comparator<? super E> comparator) b-Then write a main test. public class Sort { public static void Sort(int] list) ( Sort(list, o, list.length - 1) private static void Sort(int] list, int first, int last) if (.... int Index partition(list, first, last); Sort(list, first, Index - 1); Sort(list, Index+ 1, last); ..) { CSC311: Data Structures A-2/3

Answer please

Answer 1

Screenshot

publie clace r ATter aurt sublic static void sain(String[] args) ( t a agrt:") or(int ie itferi]-"") System.aut println"nfter sart: "); Systen.out print (arr (1)") /Sort sethod, take arr as input litiid Siti Sort(list,B, list . length-1); aca rst and Iast index of the array private static void Sortiint!1 list.int first.int l (1arstlast) eto te nt indexpartition (list, first, last); Sort(list, firat, indux - 1) Soct(list, index+1, last) ; oartition index obtaining function private static int partition ( int [list,int first, int last)
Program

//Create a class Sort
public class Sort {
   //Test main
   public static void main(String[] args) {
       int arr[] = {8,7,4,1,5,9};
       System.out.println("Before sort:");
       for(int i=0;i<6;i++) {
           System.out.print(arr[i]+" ");
       }
       System.out.println("\nAfter sort:");
       Sort(arr);
       for(int i=0;i<6;i++) {
           System.out.print(arr[i]+" ");
       }
    }
   //Sort method, take arr as input
   //Which call sort function(Quick sort)
   public static void Sort(int[] list) {
       Sort(list,0,list.length-1);
   }
   //Quick sort
   //Take array ,first and last index of the array
   private static void Sort(int[] list,int first,int last) {
       //If first less than last recursively call sort function
       if(first<last) {
           //To divide array into tw0
           int index=partition(list,first,last);
           //First half sort
           Sort(list,first,index-1);
           //Second half sort
           Sort(list,index+1,last);
       }
   }
   //Array partition index obtaining function
    private static int partition(int[] list,int first,int last) {
       //Set first element as pivot
       int pivot=list[first];
       //Starts from next element index as low
       int low=first+1;
       //Last element index as high
       int high=last;
       //Loop until low reach to high
       while(high>low) {
           //Get left half until greater than pivot
           while(low<=high && list[low]<pivot) {
               low++;
           }
           //Get right half until less than pivot
           while(low<=high && list[high]>pivot) {
               high--;
           }
           //Swap to place the small value in correct place
           if(high>low) {
               int temp=list[high];
               list[high]=list[low];
               list[low]=temp;
           }
       }
       //Check reach end
       while(high>first && list[high]>=pivot) {
           high--;
       }
       //Check pivot with high value
       //Then swap
       //Return high index as partition
       if(pivot>list[high]) {
           list[first]=list[high];
           list[high]=pivot;
           return high;
       }
       //Otherwise retun first as partition
       else {
           return first;
       }
      
    }
  
}

-----------------------------------

output

Before sort:
8 7 4 1 5 9
After sort:
1 4 5 7 8 9

-------------------------------------------

Note:-

Do you want to implement comparator and comparable using same sort?