CSI 801

Assignment #1: Sorting out Divide and Conquer

Due: September 19, 1996

Life is one long struggle in the dark.
Lucretius

Sorting Routines

Description

One of the first types of computer algorithms developed were sorting routines. Currently, there are many different types of these routines available for use. However, the efficiency of these routines can vary dramatically. In this project, you will write two sorting routines, a bubble sort and a quick sort. For each routine, you will generate an identical set of random numbers and then compare their performance sorting the list. You must write your own sorting codes for this project, however you may look at Numerical Recipies or any other sorting routines for hints in writing the code. The random number generator should be a linear congruential generator you write from scratch. This and all other programming assignments must be written in C, Fortran, or C++.

Purpose of the Assignment

This assignment will teach students the importance of recursion and bisection in Computational Sciences. Students will also learn some basic ways to approach benchmarking computer codes.

Assignment

Required Data

none.

Procedure

write a linear congruential generator (LCG) using methods discussed in class and in your textbooks
write the code to use your LCG to generate a list of N numbers where N is provided by the user
create a bubble sort routine to sort these numbers in ascending order
create a quick sort routine to sort these numbers in ascending order
using date functions in the system or in the C library, create the code to time the start and end time of the run. This can be as simple a shell script using the date function, or could use the C-library calls.
Create a plot (or plots) of the time required to sort a set of random numbers of length 50, 100, 150, 200, and 250 using these routines. (add more data if you would like). Make sure to make multiple runs for each set to get some idea of the variations. You may use any plotting routine you like for this project.
Write a short two page report summarizing your results. Include links to the plots you produced.

Assignment Requirements

The results from this project should be:

You must write your programs in C, Fortran, or C++. Graphics can be produced in any of your favorite graphics programs.
You must produce the graphs specified above. You can place the two lines on one page or on multiple pages.
You cannot use any other student's subroutines or subroutines taken directly from any commercial or freeware packages.
Be sure and summarize your results in a two-page file.
An html file called "pa1.html" should contain links to your report, your codes, and your graphics.

Plots

You should produce a plot of sorting time vs array size for both routines. You can place both data sets on a single graph, or one line on two separate graphs.

Placing it On-Line

When you have produced all the plots, create a web page for this assignment named "pa1.html and place it in your "public_html" directory. Make sure I can access it through the web. On this page, you should have links to your summary, your graphs, you programs, and the Makefile. Make sure the links work through the net.

If you absolutely cannot get the graphics into a form which can be viewed on the Web, I will accept paper copies of the assignments with no deduction in credit. However, it is much cooler to have them on-line and is more effective at showcasing your ablilities to possible employers.