Question

• Run Solver.java, where 20 array instances of 1M random integers are sorted (using Insertion- sort and Heap-sort, respectively). Solver.java is given, however the two sorting algorithms of course are implemented by yourself.

• Report the time elapsed running Solver.java, using Insertion-sort, and Heap-sort, respectively. Based on your results, comment comparatively on time-efficiency of the two sorting algorithms

• //////

• public class Solver {
     public static void main(String[] args) {
  final int SIZE = 1000000; // 1 million
  final int Instances=20;
  int[][] TwoDimArray = new int[Instances][SIZE];
    
  Sort s = new Sort();
    
  for(int i=0; i<Instances; i++) {
     s.initializeArray(TwoDimArray[i], SIZE);
     s.randomizeArray(TwoDimArray[i], SIZE);
  }
    

    
  final long startTime = System.nanoTime();
  for(int i=0; i<Instances; i++) {
  s.insertionSort(TwoDimArray[i], SIZE);
  //s.heapSort(TwoDimArray[i], SIZE);
  }
    
  final long duration = (System.nanoTime() - startTime)/ 1000000;
  System.out.println("Duration in seconds:" + (duration/1000.0));
    
  }
  }

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;
         
       }
  
       public 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;
           }
       }
  
       // 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);
           }
       }
  
  
      public void heapSort(int[] arr , int size) {
           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 void heapify(int[] arr) {
               int size=arr.length;
               for(int i=size/2-1;i>=0;i--) {
                   heapi(arr,i,size-1);
               }
          
       }

       private 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 Solver {
   public static void main(String[] args) {
final int SIZE = 1000000; // 1 million
final int Instances=20;
int[][] TwoDimArray = new int[Instances][SIZE];

Sort s = new Sort();

for(int i=0; i<Instances; i++) {
   s.initializeArray(TwoDimArray[i], SIZE);
   s.randomizeArray(TwoDimArray[i], SIZE);
}

final long startTime = System.nanoTime();
for(int i=0; i<Instances; i++) {
s.insertionSort(TwoDimArray[i], SIZE);
//s.heapSort(TwoDimArray[i], SIZE);
}

final long duration = (System.nanoTime() - startTime)/ 1000000;
System.out.println("Duration in seconds:" + (duration/1000.0));

}
}