Objective:

$$ Calculate time and space complexity of data structures and algorithms and be able to use

these complexities to choose the most appropriate for a given problem environment.

$$ Demonstrate knowledge of recursion by describing common applications and by effectively

using it to solve problems.

$$ Use of appropriate algorithms to solve common computing problems.

Problem:

In the quicksort algorithm, the pivot can be chosen using several criteria $($i$.$e$.,$ either using the first,

last or random index in the unsorted part of the array$).$ In this assignment, you will write and

compare two versions of the quicksort algorithm. First, write the partition function such that the

pivot is chosen by selecting the median of three random indexes from the array. And second, write

the partition function such that the pivot is chosen by selecting the first value from the array.

Testing:

Then you will run three tests to compare each version using an array of ten values.

Array with:

$1.$ sorted values

$2.$ random values

$3.$ reversed order array

Note: Provide very clear and easy to read in$-$line comments and your output should be clearly

labeled. Below is an example sample run with an array of randomly ordered values.

Sample run : An array with randomly ordered values

$===========$ QUICKSORT USING FIRST VALUE IN ARRAY AS PIVOT $===========$

Unsorted Array: $\{7759728275830811232\}$

Sorting the array.

Please wait $....$

Sorted Array: $\{7123032585972778182\}$

Time: $5800$ nanoseconds.

$=======$ QUICKSORT USING MEDIAN OF $3$ RANDOM VALUES IN ARRAY AS PIVOT $=======$

Unsorted Array: $\{7759728275830811232\}$

Sorting the array.

Please wait $....$

Sorted Array: $\{7123032585972778182\}$

Time: $560100$ nanoseconds.

$++++++++++++++++++++++++++++$ END OF SORTING $++++++++++++++++++++++++++++++$

In Java