use java

Performance studies of sorting algorithms. Before you start the coding, make sure that you are familiar with the timing functions provided by Java. You may use the difference between two

System.currentTimeMillis()

to compute the elapsed time between the two call.

long start = System.currentTimeMillis(); // sequence of operations long end = System.currentTimeMillis();

Problem 1: comparison of sorting algorithms

In this task, you are going to study the performance of the following sorting algorithms:

quicksort

insertion sort

quicksort combined with insertion sort when the array size is smaller than 20.

Experiment your implementations with the following data sets:

Size of data setcomplete random10% out of order1% with at most 10 out of order

100

1000

10000

100000

200000

You should write a short report(about a page) with the following information:

Have a separate function to generate the needed data set. Explain how you generated data for 10% and 1% out of order. Efficiency is NOT important for generating the data set.

Produce a table with results from the above data sets and briefly discuss your results.