Question

Problem Description:

Problem Description:

Write a program that obtains the execution time of Selection sort, Insertion sort, Merge sort for input size 50000, 100,000, 150,000, 200,000, 250,000, and 300,000. Your program should create data randomly and print a table like this:

Array Size	Selection sort	Insertion sort	Merge sort
50000
100000
150000
200000
250000
300000
2000000
3000000
4000000

(Hint: You can use the code template below to obtain the execution time.)

long startTime = System.currentTimeMillis();

perform the task;

long endTime = System.currentTimeMillis();

long executionTime = endTime - startTime;

Analysis:

(Describe the problem including input and output in your own words.)

Coding: (Copy and Paste Source Code here. Format your code using Courier 10pts)

Name the public class Exercise18_29

Testing: (Describe how you test this program)

Answer 1

//Java program

import java.util.Random;

public class Sorting {
   public static void main(String args[]) {
       int n;
       long startingTime,endingTime;
       Random rand = new Random();
       int sizes[] = {50000, 100000, 150000, 200000, 250000,300000};
       System.out.println("Array Size\tSelection sort\tInsertion sort\tMerge sort");
       for(int j=0;j<sizes.length;j++) {
           n = sizes[j];
           System.out.print(n+"\t\t");
           int arr[] = new int[n];
           int temp[] = new int[n];
           int temp1[] = new int[n];
          
           for(int i=0;i<n;i++) {
               arr[i] = rand.nextInt(10000);
               temp[i] = arr[i];
           }
          
           startingTime = System.currentTimeMillis();
           selectionSort(temp,n);
           endingTime = System.currentTimeMillis();
           System.out.print(endingTime - startingTime+"\t\t");
          
          
          
           for(int i=0;i<n;i++) {
               temp[i] = arr[i];
           }
          
           startingTime = System.currentTimeMillis();
           insertionSort(temp,n);
           endingTime = System.currentTimeMillis();
           System.out.print(endingTime - startingTime+"\t\t");
          
           for(int i=0;i<n;i++) {
               temp[i] = arr[i];
           }
      
           startingTime = System.currentTimeMillis();
           mergeSort(temp,temp1,0,n-1);
           endingTime = System.currentTimeMillis();
           System.out.println(endingTime - startingTime);
          
          
       }
  
      
   }
  
   //Merge function
       public static void merge(int a[],int temp[],int l,int m,int r){
           int temp_pos=l,size=r-l+1,left_end=m-1;
           while(l<=left_end&&m<=r){
               if(a[l]<a[m])temp[temp_pos++]=a[l++];
               else temp[temp_pos++]=a[m++];
           }
           while(l<=left_end)temp[temp_pos++]=a[l++];
           while(m<=r)temp[temp_pos++]=a[m++];
           for(int i=0;i<size;i++){
               a[r]=temp[r];
               r--;
           }
       }
       //mergesort function
       public static void mergeSort(int a[],int temp[],int l,int r){
           if(l<r){
               int mid=l+(r-l)/2;
               mergeSort(a,temp,l,mid);
               mergeSort(a,temp,mid+1,r);
               merge(a,temp,l,mid+1,r);
           }
       }
      
       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;
           }
       }
       public static void selectionSort(int a[],int n){
           int min;
           for(int i=0;i<n-1;i++){
               min=i;
               for(int j=i+1;j<n;j++)if(a[j]<a[min])min=j;
               if(min!=i){
                   int temp=a[i];
                   a[i]=a[min];
                   a[min]=temp;
               }
           }
       }
      
      
}