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.