CPSC 215 Lab 1, 9/2/99: Swap Sort

Due Thuesday, 9/7/99


This lab is intended for you to:
  1. review some basic programming skills
  2. learn and use file I/O
  3. conduct experiments on the efficiency of algorithms

For part one of the lab you need to implement program to sort an array of integers in a fixed range (e.g., 0 through 19) using the "swap sort" technique described in class, and reviewed here:

For example, assume A = {12,5,14,5,11,12,18,2,4,5}. You need to first create a method "int findmindex(int startIndex)" that searches the array starting from startIndex, and returns the INDEX of the smallest number that it encountered. Be sure that you understand that findmindex returns the INDEX, or the position in the array that the smallest number was found, and not the number itself. Your program will contain a primary loop for(i=0;i<A.length;i++) that steps through the array, and for each step, call findmindex(i), which will return the index of the smallest number in the array starting from initial index i. You then swap the smallest number with the original ith element.

So during the first iteration of the loop (i=0), you will call findmindex(0) which will return 7, which is the array index where the smallest number (2) is stored. You then swap 7 with A[0], which will leave you with

A = {2,5,14,5,11,12,18,12,4,5}

During the second iteration of the loop (i=1), you will call findmindex(1), which will return 9, the index of the smallest element (4) of the array starting at index 1. You then swap 4 with A[1], giving you

A = {2,4,14,5,11,12,18,12,5,5}

Note that now the first two elements are in the right order. After the last iteration of the loop, you will have a sorted array:

A = {2,4,5,5,5,11,12,12,14,18}

Refer to the sample program posted on the web page for help.


Part 2 of the assignment asks you to conduct several experiments on the running time of your algorithm. You are to create five data files containing 1000, 2000, 3000, 4000, and 5000 randomly generated integers (between 0 and 9999). The code to create and read these files have been provided for you. Use the System.currentTimeMillis() function to find out how much time it took for your algorithm to work. Be sure that the timing samples are taken immediately before and after the call to your method. Also, make sure that no printing or IO of any kind is performed between time samplings, as these operations usually take much longer than pure computation.

Run all experiments on the same machine. Make sure all other applications (editors, web browsers, etc...) are closed before running your program. For each sample data file, run your program at least five times, and record the best result. This should help to factor out unforseen operating system interference while your program is running. It should be emphasized that each file should be created only ONCE - for example, you should create a file with 2000 integers ONCE, then comment out the makedata method call before running more tests and taking the best result.

Your are then to prepare a lab report following the format of the attached sample. List your data in the report, and plot them on a chart. Be neat. Answer the following questions:

  1. Observe that, on my chart for bubble sort, when the size of the array doubled from 1000 to 2000 integers, the running time increased more than 5 times. Please try to explain this disproportionate increase in running time.
  2. Did you observe the same behavior with the algorithm you implemented? Why did your algorithm behave similarly or differently? Does your graph form a curve like bubble sort, or is it more of a straight line?
  3. Based on these considerations, which algorithm do you think is more efficient in terms of running time, and why? Are there tradeoffs between the algorithms?
  4. Please feel free to report any additional thoughts and conclusions you might have.