The Objective

The objective of this assignment is to give you some practice writing functions and using top-down design, separate compilation, and random numbers. This project will give you the opportunity to compare some well-known sorting and searching methods.

The Background

Searching and sorting are common activities in programming. The speed of the search method is extremely important, since often the information being searched for has been requested by a customer who is waiting.

There are many known algorithms for sorts. Some of them are quite complicated, but two of them are easy enough for beginners to understand and code. These are the bubble sort and the selection sort.

The two searching techniques are linear search and binary search. Binary search is extremely fast and also easy to understand and code. That's why binary search is typically the search method of choice for programmers.

The Task

You are to write a program that takes input from a data file using unix redirection, as in a.out < p2data1.dat and fills 2 one-dimensional arrays with the values found in the file. Each of these 2 arrays will be identical. You will pass one of these unsorted arrays to each of the different sorting functions you'll write. I guarantee that there will be exactly 100 integers in each of these files.

In a file called sort.c, you will have 2 different sort functions. One that implements bubble sort and one that implements selection sort. Both of these functions must sort the array passed to it and return the number of swaps that were necessary to get the array in sorted order. Code for bubble sort can be found in the book and code for selection sort is shown in Lecture 10.

In a file called search.c, you will have functions for the 2 types of searching, linear search and binary search. Each of the functions must return the number of elements that were examined before the target number was found. Code for binary search can be found in Lecture 10. You must also have a function that picks a random number in the range of 0 to 99, which is to be used as the index into the sorted array. You will use the value found in that element as the value you'll search for using the two different methods. This function should also be in the file search.c

The program should generate a report that shows the original unsorted values, the sorted values and then an analysis of the sorts and searches.

Sample Output

Submitting the Program

To submit the file you should use the command:

submit cs201 proj2 proj2.c sort.c search.c sort.h search.h

You can check your submission by using the command:

submitls cs201 proj2 [an error occurred while processing this directive] Friday, 27-Feb-1998 15:12:53 EST