Project 3: Sorting arrays

The goal of this project is to implement basic sorting algorithms. This will review and reinforce your understanding of how to manipulate arrays as well as give you practice in the basic syntax of writing methods.

SPECIAL NOTE

Beginning with this project, documentation and style will be assessed as part of your grade. Make sure you conform to conventions for identifiers and properly document all parts of your program.

1. Introduction and set-up

The handout on sorting describes what computer scientists mean when we talk about sorting data. That handout also describes three algorithms for sorting arrays of integers.

Move into the directory where you put files for this class, and then clone the repository to get the starting code:

$ hg clone /cslab/class/csci235/projects/project3

Now you can cd into the project3. You should find four Java source files there. Sort.java provides the main method for this assignment; it includes some parts that you don't need to understand, but it allows you to exercise any .java file that provides a suitable method sort().

The other three Java files will each provide a sort() method. Bubble.java is already filled in, with the method that we wrote in class on Monday. To run it, you need to compile both Sort.java and Bubble.java, then run

$ java Sort Bubble

This will create an array filled with random values and display it. It then calls the sort method in Bubble and prints the array again after that. If we got it right in class, we should see that the second time it prints in ascending order.

Take some time to read the bubble sort method and compare it to the description from the handout.

Your task is to complete the other two sorting methods to use the appropriate algorithms.

2. Selection Sort

Consult the handout for a description of selection sort.

Open the file Selection.java in Emacs. You'll see that it contains an empty method sort(). You will need to fill in the method. You can compile and run the program now.

$ javac Selection.java
$ java Sort Selection

The program won't crash, but it won't sort the array either. Remember that anytime you make a change to Selection.java, that's the file you need to recompile, but you do not need to recompile Sort.java (because you're not going to make any changes to it).

Follow these steps to write a selection sort program:

1. Write a loop that simply finds the smallest value and prints it out. Since finding a smallest value is part of selection sort, this is a way to break down the problem—plus it's review. If you compile an run at this point, you'll see that the array doesn't change before or after your method runs, but the smallest value of the array is printed out.
2. Next change what you've done so that your program does not ever record the smallest value, but instead records (and prints) the position (ie, index) of the smallest value.
3. Finally, the loop you have written so far must become the inner loop of the larger algorithm. Write the outer loop, which iterates over the array and, at each iteration, finds the position of the smallest unsorted value and swaps it with the value at the current position (notice that for each iteration of the outer loop, the current position is the first position in the unsorted section). Hint: you will have to change the starting index of the inner loop for this to work.

Compile and test. When you're confident it is working correctly, commit it to your repository before you move on.

3. Insertion sort

To set up this part, open the file Insertion.java. See the handout for a description of insertion sort, but you'll need to figure out how to proceed. This algorithm will also involve a loop within a loop.

• Over what does the outer loop vary?
• The inner loop does the insertion—and the scooting. How does its counter change?

Complete the method.

If you want to test just part of it, you can write your own main() method at the end of Insertion.java. If you do that, you might find it helpful to call one or both of the methods provided by Sort.java to randomly fill an array or to print it out. For that you'd run

$ java Insertion

When you have it complete, test it by running it using Sort as the driver:

$ java Sort Insertion

4. Turn in

Create a script file that shows you compiling Sort.java plus the two files that you have written. Then run each sort a couple of times.

Hand in your source files and script electronically as project3.

DUE: Friday, Feb. 19, at 5:00 PM.