Using java create the following program 1 Sorting Create 3 text files, one with

Question

Using java create the following program

1 Sorting Create 3 text files, one with the 50000 integers 1 through 50000 in order, one with the 50000 integers 1 through 50000 in reverse order, and one with 50000 random integers (between 1 and 50000). Write a program to

         Read the name of a file

         Store the contents of the file into a 50000 element array,

         Sort the array using an Insertion Sort, and

         Print the actual running time (without any server overhead) of the sort.

         Print the number of comparisons used in the sort.

         Print just the first 30 values in the resulting array

Turn in a printed copy of the program, along with a printout of the output from three separate runs (using the three text files). Implement the Bag class for a bag of integers as described in the file

            Chap02 Bag Class.ppt

posted in the folder Lecture Notes on the class website. Also create a driver class similar to that for the Die class above to show that the Bag class works.

2 Big_OH Notation Consider the following functions:

n+sin(n)    4n2     log3n      3n      20n      2      log2n      n2/3

(a) Arrange the six expressions by asymptotic growth rate from slowest to fastest.

(b) Graph the following six functions on a single plot varying n from 1 to 10.

n+sin(n)    4n2     log3n      3n      2             n2/3

Explanation / Answer

import java.io.*;

import java.util.*;

class insertionSortTimes

{

public static double insertionSort(String fileName)throws FileNotFoundExecption

{

int[]list =new int[50000];

double t1,t2;

//store the contents of the file in to 50000 element array

Scanner sc = new Scanner(new File(fileName));

for(int i =0; i<50000;i++)

list[i] = sc.nextint();

//Sort the array using an insertion Sort

t1 = System.currentTimeMillis();

int temp;

int comparisons = 0;

for(int i= 0;i<list.length;i++)

{

temp = list[i];

int j;

for(j = i-1;j>=0 &&list[j]> temp;j--)

{

comparisions++;

list[j+1] = list[j];

}

list[j+1] = temp;

}

t2 = System.currentTimeMillis();

//print the number of comparisons used in the sort

System.out.println("the number of comparisons required here is :"+comparisons);

//print just the first 30 values in the resulting array

for(int i = 0;i<30;i++)

System.out.print(list[i]+"");

Sysem.out.println();

return t2-t1;

}

public static void main(String[]args)throws FileNotFoundException

{

//Read the name of a file

Scanner console = new Scanner(System.in);

System.out.print("enter the name of the sorted file:");

String fileName= console.next();

//print the actual running time (without any server overhead)of the sort

System.out.println("time to sort the readily soted file:"+insertionSort(fileName)+"sec/n/n");

System.out.print("enter the name of the reverse sorted file:");

fileName = console.next();

System.ou.println("time to sort the reverse sorted file :"+insertionSort(fileNmae)+"sec/n/n");

System.out.print("enter the name of the randomly sorted file:");

fileNmae = console.next();

System.out.println("time to start the randomly sorted file:"+insertionSort(fileName)+"sec/n/n");

}

}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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