Write a program that obtains the execution time of selection sort, insertion sor

Question

Write a program that obtains the execution time of selection sort, insertion sort, bubble sort, merge sort, quick sort, and radix sort. Your program should test all sort methods for input sizes of 10000, 20000, 30000, 40000, 50000, and 60000. The selection sort, bubble sort, and radix sort should also be tested for input sizes 100000 and 200000.

The program should create the data that is sorted from randomly generated integers and should output the results in a table identical to the one below.

(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;

Explanation / Answer

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package cheggprograms;

import java.util.Random;

/**
*
* @author Laasya
*/
public class CheggSotingProgram {
  
static int asizes[]=new int[]{10000,20000,30000,40000,50000,60000,100000,200000};
static int a[]=new int[200000];
static int temp[]=new int[200000];
static int b[]=new int[200000];
static int c[]=new int[200000];
static int d[][]=new int[200000][200000];
static int i,j;
static int svalues[]=new int[]{0,0,0,0,0,0,0,0};
static int ivalues[]=new int[]{0,0,0,0,0,0,0,0};
static int qvalues[]=new int[]{0,0,0,0,0,0,0,0};
static int mvalues[]=new int[]{0,0,0,0,0,0,0,0};
static int bvalues[]=new int[]{0,0,0,0,0,0,0,0};
static int rvalues[]=new int[]{0,0,0,0,0,0,0,0};
public static void main(String args[])
{
  
CheggSotingProgram csp=new CheggSotingProgram();
  
for(int i=0;i<asizes.length;i++)
{
int c=0;
Random r=new Random(asizes[i]);
  
while(c<asizes[i])
{

a[c]=r.nextInt(asizes[i]);
c++;
}
System.out.println(c);
if(asizes[i]<700)
{
  
csp.bubblesort(c);
  
csp.insertionsort(a,c);
csp.selectionsort(c);
csp.mergesort(c);
csp.radixsort(c);
csp.quicksort(0,a.length-1,c);
}
else
{
csp.selectionsort(c);
csp.bubblesort(c);
csp.radixsort(c);
}

}
System.out.println("Array Size Selection Sort Insertion Sort Bubble Sort Merge Sort Quick Sort Radix Sort ");
for(i=0;i<bvalues.length;i++)
{
System.out.println(asizes[i]+" "+svalues[i]+" "+ivalues[i]+" "+bvalues[i]+" "+mvalues[i]+" "+qvalues[i]+" "+rvalues[i]);
}   
}
public void insertionsort(int a[],int c)
{
long starttime=System.currentTimeMillis();
for(int i=1;i<c;i++)
{
int k=a[i];
int j;
for(j=i-1;j>=0&&k<a[j];j--)
{
a[j+1]=a[j];
   }
   a[j+1]=k;
}
long endtime=System.currentTimeMillis();
long time=endtime-starttime;
ivalues[c]=(int)time;
}
public void bubblesort(int c)
{
  
long starttime=System.currentTimeMillis();
int i,j,temp;
  
       for(i=1;i<c;i++)
       {
  
  
           for(j=0;j<c-(i+1);j++)
           {
    if(a[j]>a[j+1])
               {
                   temp=a[j];
                   a[j]=a[j+1];
                   a[j+1]=temp;
               }
           }
  
       }
long endtime=System.currentTimeMillis();
long time=endtime-starttime;
bvalues[c]=(int)time;
}
public void selectionsort(int c)
{
long starttime=System.currentTimeMillis();
for(i=0;i<a.length;i++)
{
int s=i;
for(j=i+1;j<a.length;j++)
{
if(a[s]>a[j])

s=j;
}
if(i!=s)
{
int temp=a[i];
a[i]=a[s];
a[s]=temp;
}
}
long endtime=System.currentTimeMillis();
long time=endtime-starttime;
svalues[c]=(int)time;
}
public void mergesort(int c)
{
long starttime=System.currentTimeMillis();
for(int s=1;s<a.length;s=s*2)
{
int l1=0,k=0;
  
while(l1+s<a.length)
{
   int h1=l1+s-1;
   int l2=h1+1;
   int h2=l2+s-1;
   if(h2>=a.length)
   h2=a.length-1;
int i=l1;
int j=l2;
while(i<=h1&&j<=h2)
{
   if(a[i]<=a[j])
   temp[k++]=a[i++];
   else
   temp[k++]=a[j++];
   }
   while(i<=h1)
   temp[k++]=a[i++];
   while(j<=h2)
   temp[k++]=a[j++];
   l1=h2+1;
}
for(int i=l1;k<a.length;i++)
   temp[k++]=a[i];
   for(int i=0;i<a.length;i++)
   a[i]=temp[i];
long endtime=System.currentTimeMillis();
long time=endtime-starttime;
mvalues[c]=(int)time;
   // printf(" size=%delements are :",s);
   // for(i=0;i<n;i++)
//   printf("%d,",a[i]);
}

}
public void quicksort(int lb,int ub,int c)
{
long starttime=System.currentTimeMillis();
int ref,i,j,temp;
boolean flag=true;
if(lb<ub)
{
   i=lb;
   j=ub+1;
   ref=a[i];
   while(flag)
   {
   i=i+1;
   while(a[i]<ref)
       i=i+1;
  
j=j-1;
   while(a[j]>ref)

   j=j-1;
   if(i<j)
   {
       temp=a[i];
       a[i]=a[j];
       a[j]=temp;
   }
   else
   flag=false;
   }
temp=a[lb];
a[lb]=a[j];
a[j]=temp;
quicksort(lb,j-1,c);
quicksort(j+1,ub,c);
}
long endtime=System.currentTimeMillis();
long time=endtime-starttime;
qvalues[c]=(int)time;
}
  
  
public void radixsort(int f)
{
long starttime=System.currentTimeMillis();
int p=0;
int x;
int z;
for(int i=0;i<10;i++)
c[i]=0;
while(p<5)
{
for(i=0;i<a.length;i++)
{
x=a[i];
j=0;
while(x>0)
{
   b[j]=x%10;
   x=x/10;
   j++;
}
d[c[b[p]]][b[p]]=a[i];
c[b[p]]++;
for(z=0;z<5;z++)
   b[z]=0;
}
int k=0;
for(i=0;i<10;i++)
{
for(j=0;j<c[i];j++)
{
   a[k]=d[j][i];
   k++;
   }
}
for(i=0;i<10;i++)
c[i]=0;
for(i=0;i<a.length;i++)
for(j=0;j<10;j++)
d[i][j]=0;
p++;
}
long endtime=System.currentTimeMillis();
long time=endtime-starttime;
rvalues[f]=(int)time;
}

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.