Java assignment programming

Problem Description

Write a program to implement bubble sort, insertion sort, selection sort, merge sort and quick sort (pivot = random index) algorithms.

a) Compute the CPU processing time for all the algorithms for varying input sizes as follows: N = 102,

103, 104, 105, and 106

b) Use a random number generator to generate the inputs. Obtain the inputs from the following input ranges: 1- 103, 1 - 106, 1 – 109, 1 - 1012

c) Write down your results as a table (with varying input size and algorithm type) and plot the graph. Present your inferences and/or explanations for your result (in a separate document).

A program heading in the following format should begin your program:

//==============================================================

// Program 3 – Sorting Program

//==============================================================

// <your name>

// <class section>

// <date>

//--------------------------------------------------------------

Grading

Documentation 10%

Style 10%

Exception Handling 10%

Correctness 70%

References: http://java.sun.com/j2se/1.5.0/docs/api/java/lang/System.html (Java) http://bytes.com/topic/c/answers/221638 - using - clock - measure - run - time (C++)

1

Dr. Subrata Acharya Towson University

Time Measurement

In Java:

long startTime;

long stopTime;

...

startTime = System.currentTimeMillis(); //do whatever you want to measure stopTime = System.currentTimeMillis();

System.out.println("Elapsed time = "+(stopTime-startTime)+" msecs.");

In C++:

#include <ctime> clock_t start,finish; double time; start = clock(); sort something finish = clock();

time = (double(finish)-double(start))/CLOCKS_PER_SEC;

In C:

#include <sys/types.h> #include <time.h> time_t t1,t2; int elapsed_time; (void) time(&t1); sort something (void) time(&t2);

elapsed_time = (int) t2-t1;

2