## CS 2401 Assignments #8-10

**Due Dates:** Different for different parts of this
assignment.
**Objective:** The goal of this assignment is to practice
searching, sorting, and runtime estimations.

**Assignment:** write the following programs:

- a program for linear search and a program for
binary search - by November 8 or 9,
depending on the day of your lab;
- a program for bubble sort, a program for selection sort, and
a program for insertion sort - by November
15 or 16, depending on the day of your lab;
- a program for quicksort, a program for
merge sort, and a program for heap sort -
by November
22 or 23, depending on the day of your lab.

It is sufficient to write a program that only works for arrays of
integers.
Each program must also

- automatically count the number of
comparisons and
assignments, and
- estimate the computation time (just like we did
in one of the previous lab assignments).

*Clarification*: an *assignment* is when you assign a new
value to a variable, e.g., a = 3 is an assignment.

Test your programs on random arrays of at least five different sizes,
including at least one larger than 100 elements. Use Java
random number generators to generate random elements of these arrays.
(To test binary search, you need a sorted array; to get a sorted
array, use Java's Arrays.sort() method
to sort your randomly generated array.)
Compare the resulting numbers of comparisons and assignments
with the theoretical bounds provided by the textbook.