Question

In this programming question, n integers ranging from 0 to n-1 are stored randomly in A, an array of size n. In the class Sort.java, you are supposed to implement the following two sorting algorithms: Insertion-sort and Heap-sort. You have to work directly on the given starter code.

• Download the starter code from the course web site. Read the starter code and make sure you understand how it works before attempting to modify it. In the given class Sort.java, Selection-sort is already implemented and is used to sort an array of numbers from 0 to 9.

  Initially, the array is: 0123456789

  After randomization, the array becomes: 8201954367

       SELECTION SORT...
  

  The array is now sorted: 0123456789

• Implement Insertion-sort and Heap-sort in the Sort class.

• ////////

• import java.util.Random;

  public class Sort {
        
     // swap the ith element with the jth elements.
     private void swap(int[] a, int i, int j){
         int temp;
         temp = a[i]; a[i] = a[j]; a[j] = temp;
     }
    
     // initialize the array a with elements from 0 to size-1.
     public void initializeArray(int[] a, int size){
         for (int i=0; i            a[i]=i;
         }
     }
    
     // display the elements in the array a, rowSize elements per row.
     public void displayArray(int[] a, int size){
         int rowSize=100;
         for (int i=0; i            if(i%rowSize==0){
                 System.out.println();
             }
             System.out.print(a[i]+ " ");
         }
         System.out.println();
     }
    
     // randomly swap two elements in a for SWAPTIMES times.
     public void randomizeArray(int[] a, int size){
         final int SWAPTIMES = 10000;
         Random r = new Random();
  int j, k;
  for(int i=0; i< SWAPTIMES; i++){
     j = r.nextInt(size);
     k = r.nextInt(size);
     this.swap(a, j, k);
  }
     }
    
    
     // selectionSort
     public void selectionSort(int a[], int size){
         int i, j, min, minIndex;
         for (j=0; j            minIndex=j; min = a[j];
             for (i=j+1; i                if(a[i] < min ){minIndex=i; min = a[i];}
             }
             this.swap(a, j, minIndex);
         }
     }
    
  }   

• ////

• public class Starter{
     public static void main(String[] args) {
  final int SIZE = 10;
  int[] array = new int[SIZE];
    
  Sort s = new Sort();
    
  s.initializeArray(array, SIZE);
  System.out.print("Initially, the array is:");
  s.displayArray(array, SIZE);
    
  System.out.println();
  System.out.print("After randomization, the array becomes:");

  s.randomizeArray(array, SIZE);
  s.displayArray(array, SIZE);
  System.out.println("\nSELECTION SORT...\n");
  System.out.print("The array is now sorted:");

  s.selectionSort(array, SIZE);
  s.displayArray(array, SIZE);

    
  }
  }
  

Answer 1

//Java program

import java.util.Random;

class Sort {
    
   // swap the ith element with the jth elements.
   private void swap(int[] a, int i, int j){
       int temp;
       temp = a[i]; a[i] = a[j]; a[j] = temp;
   }

   // initialize the array a with elements from 0 to size-1.
   public void initializeArray(int[] a, int size){
       for (int i=0;i <size;i++) a[i]=i;
     
   }

   // display the elements in the array a, rowSize elements per row.
   public void displayArray(int[] a, int size){
       int rowSize=100;
       for (int i=0; i <size;i++) {         
           if(i%rowSize==0){
               System.out.println();
           }
           System.out.print(a[i]+ " ");
       }
       System.out.println();
   }

   // randomly swap two elements in a for SWAPTIMES times.
   public void randomizeArray(int[] a, int size){
       final int SWAPTIMES = 10000;
       Random r = new Random();
       int j, k;
       for(int i=0; i< SWAPTIMES; i++){
           j = r.nextInt(size);
           k = r.nextInt(size);
           this.swap(a, j, k);
       }
   }
   //Insertion Sort
   public static void insertionSort(int a[],int n){
       for(int i=1;i<n;i++){
           int j=i-1,val=a[i];
           while(j>=0&&a[j]>val){
           a[j+1]=a[j];
           j--;}
           a[++j]=val;
       }
   }

   // selectionSort
   public void selectionSort(int a[], int size){
       int i, j, min, minIndex;
       for (j=0; j < size-1 ;j++) {       
           minIndex=j; min = a[j];
           for (i=j+1; i<size;i++) {            
               if(a[i] < min ){minIndex=i; min = a[i];}
           }
           this.swap(a, j, minIndex);
       }
   }
   //HeapSort
   public static void heapSort(int[] arr) {
       int size=arr.length;
       heapify(arr);
       while(size>0) {
           int temp = arr[0];
           arr[0]=arr[size-1];
           arr[size-1] = temp;
           size--;
           heapi(arr,0,size-1);
       }
      
   }

  

   private static void heapify(int[] arr) {
           int size=arr.length;
           for(int i=size/2-1;i>=0;i--) {
               heapi(arr,i,size-1);
           }
      
   }

   private static void heapi(int[] arr, int i,int size) {
       int left=2*i+1;
       int right=2*i+2;
       int s=i;
       if(left<=size&&arr[left]>arr[i]) {
           s=left;
       }
       if(right<=size&&arr[right]>arr[s]) {
           s=right;
       }
       if(i!=s) {
           int temp=arr[i];
           arr[i]=arr[s];
           arr[s]=temp;
           heapi(arr,s,size);
       }
              
      
   }

}

////

public class Starter{
   public static void main(String[] args) {
final int SIZE = 10;
int[] array = new int[SIZE];

SSort s = new SSort();

s.initializeArray(array, SIZE);
System.out.print("Initially, the array is:");
s.displayArray(array, SIZE);

System.out.println();
System.out.print("After randomization, the array becomes:");

s.randomizeArray(array, SIZE);
s.displayArray(array, SIZE);
System.out.println("\nSELECTION SORT...\n");
System.out.print("The array is now sorted:");

s.selectionSort(array, SIZE);
s.displayArray(array, SIZE);

System.out.println();
System.out.print("After randomization, the array becomes:");

s.randomizeArray(array, SIZE);
s.displayArray(array, SIZE);
System.out.println("\nHEAP SORT...\n");
System.out.print("The array is now sorted:");

s.heapSort(array);
s.displayArray(array, SIZE);

}
}

//sample output