COMP – 10205 – Data Structures and Algorithms

You ha
ve be
en
provided
with starter code
(see
MyCanvas
)that in
cludes the source code for
each of the

sort
methods
discussed (bubble,
sel
ection, ins
ertion
, shell,
merge
, quick and
radix
) that
are to
be evaluated
.
You must add code to each of the methods to count
the number of comparisons
required to completely sort the data.
Ensure that you generate and use the same data for each
sort.
Remember that the sort methods replace the existing
data (in place sorting) s
o you need
to copy over
the sorted output array
before each sort is called. You will also
measure the tim
e
required to sort the data using each method by
timing the algorithm using the
System.nanotime
method.
Requirements
Your program must report the following inf
ormation:
1.
The time required
in microseconds
, the number of comparisons required and the time
to execute a basic step (the comparison) in
ns for each of the sort
methods provided
.The basic step is determined by taking the time
required to sort an array of a size
n anddividing by the number of
basic steps f
or that algorithm. Report your results for data
sets of
2
0, 100
, 10000
, 5
0000
elements.

Produce a table that looks similar to this:
Comparison for array size of
20
(Aver
aged over 5 runs)
====================
==================
====================
Sort Execution Time
Compares
Basic
Step
Algorithm
(ns) (ns)-
———————————————————-aSort
xxx
xxxxx
xxx.x
bSort xxx xxxxx xxx.xcSort xxx xxxxx xxx.xdSort xxx xxxxx xxx.xeSort xxx xxxxx xxx.xfSort xxx xxxxx xxx.xgSort xxx xxxxx xxx.x———————————————————–You will need to produce a table for each different data size. The
results should be
averaged over a number of runs in order to get reliable results.
2.
Create a random array of 100,000 positive integer values and then compare the
performance of using a linear search (method a) vs a sort/binary search (method b) of
the ar
ray. Search the array for
-1 (it will not be found in the array). Use one of the 7
sorting techniques provided. Report the time required for both techniques and also
report the number of linear searches required that would justify sorting the data first
.3.
In a
Comme
nt section at the TOP of your source file
, provide
answers to the following:
a. List in order (fastest to slowest) your selection of algorithm to use when the arrayto be
sorted
contains 20 elements. Base this on your results
b.
List in order (fastest to slowest) your selection of algorithm to use when the arrayto be sorted contains 50000 elements.c.
At 50000 elements which sort has the lowest basic instruction set time? Does this
impact your selection of the fastest algorithm?
Why?
d. In a table provide the following information for each algorithm:

Name BIG O notation
(time complexity
– average case)
 BIG O notation (space
complexity
– worst case)
Example Output
to include in c
omment
Sort Algorithm Identification
==========================================================Sort Sort Algorithm Big O Big OAlgorithm Name (time)
(space)———————————————————–aSort ________
O(___)
O(____)
bSort ________ O(___) O(____)cSort ________ O(___) O(____)dSort ________ O(___) O(____)eSort ________ O(___) O(____)fSort ________ O(___) O(____)gSort ________ O(___) O(____)———————————————————–

Implementation Notes:Part 1: You will need to make each method return the count – change the type of method from avoid to a long method. To get counting to work without using a global variable, you will need to use recursivecounting in some of the methods. An example of recursive counting is shown below:/*** A demonstration of recursive counting in a Binary Search* @param array – array to search* @param low – the low index – set to 0 to search whiole array* @param high – set to length of array to search whole array* @param value – item to search for* @param count – Used in recursion to accumulate the number of comparisons made*(set to 0 on initial call)* @return an array with the item index in the first value and the*count in the second value*/private static int[] binarySearchR(int[] array, int low, int high, int value, intcount){ int middle;// Mid point of search// Test for the base case where the value is not found.if (low > high)return new int[] {-1,count};// Calculate the middle position.middle = (low + high) / 2;// Search for the value.if (array[middle] == value)// Found match return the indexreturn new int[] {middle, count};else if (value > array[middle])// Recursive method call here (Upper half of remaining data)returnbinarySearchR(array, middle + 1, high, value, count+1);else// Recursive method call here (Lower half of remaining data)returnbinarySearchR(array, low, middle – 1, value, count+1);} The code to do the counting should be modularized so that code duplication is minimized.You can use method references (function pointers), and try to create a loop for each of thearray sizes requested.

NOTE: I have uploaded one starter file for the use and help in Assignment please use it properly.