CSC 212: Programming with Data Structures

Homework 4: Sorting 1

Due: Wednesday, Feb. 24, 11:59pm

In this homework, we will be using the LinkedList class we developed in Lab 4 for a purpose. (So this is the distinction between implementing a data structure and using or programming with a data structure.) The specific purpose will be sorting, and we'll see how often data structures and algorithms can go hand in hand.

Because implementing these sorting algorithms is very foundational and important in computer science, others have done it before. Please make sure to write only original code and refrain from looking at sources with implementation code. Doing so will allow you to have this valuable experience that no computer scientist should be without.

For this assignment you may work with a partner, using good pair programing practices (switch every 30 minutes, the non-keyboard partner is the main driver, telling the keyboard partner what to write). However, they must be a different person than Homework 2 (but can be the same as Lab 4).

To begin, download the following file and copy over your Node.java and LinkedList.java from Lab 4.

SortingApp.java

Insertion Sort

Insertion sort is a simple sorting algorithm where we build up the sorted list gradually. In this version of insertion sort, we'll first start out with an array. First we just take the first element of the unsorted array and create a list with just that element. Then we'll take the second element of the unsorted array and compare that with every element in the list, placing it in the correct position. We'll continue adding elements (at their correct position) until we've sorted the entire array.

  1. To build up this algorithm, first we need to make a few changes to Node.java and LinkedList.java. Instead of using a generic "Object", we'll change it so that the "data" within our nodes are always Strings. So whenever there is an Object in either of these classes, change it to String. This will allow us to compare Strings easily, which we need to do for sorting.

  2. Next write a toString() method in LinkedList that will return a string representation of the elements in the list. (Look back on Homework 1.) You should tag this method with the @Override keyword. 
     
@Override
public String toString() {
	// TODO
}

  3. Then, add an insertionSort method to SortingApp: 
    
private static LinkedList insertionSort(String[] array) {
	// TODO
}
    This will take in an array of Strings, but return a list of Strings, showing uses of these two data structures. It is very helpful to have a list for insertion sort since we are gradually adding elements at different positions. To compare two strings to see which comes first alphabetically, use the compareTo() method (investigate String Javadocs for more information about this method).

    Within your sorting method, make sure to print out the list as it's being developed. So for this example, the output in this example should look like: 

    
hi 
hi how 
are hi how 
are hi how you 
are hi how today you
  4. Finally we will sort the students in 212 by name (currently you are all sorted by account number). Uncomment this part in main and make sure your method works in this case. Add a boolean argument to insertionSort to tell the method whether or not to print intermediate output. For the first example, print all the steps. For the second example, just print the final sorted list.

Insertion sort with Romanian folk dance

Note that this dance implementation is in-place, but your implementation should use a linked list so as not to override the original array of elements.

Bubble Sort

Bubble sort with Hungarian folk dance

Now we'll do the same thing again (for both examples), using bubble sort instead. Bubble sort starts by comparing the first two elements in the list, then swapping them if they are out of order. Then it moves on to the 2nd and 3rd elements, again swapping them if they are out of order. It continues through the list, ultimately resulting in the last element being in place (i.e. "bubbling" to the top). Then it starts all over again!

This algorithm can be done "in place" with the existing array, or it can be done by building a new list. Think about the merits and implementation issues of each approach, and then implement your choice as a new method in main. Make sure you get the same output with each type of sorting algorithm!

Runtime Analysis

Finally, we will compare the runtime of these two algorithms. This part is open-ended and you might spend some time thinking about how to best test this. I'll outline an example method, but feel free to modify it or create a new method. Regardless of your method, the end goal should be a graph showing how the runtime changes as the length of the lists gets longer.

  • Create a method in main that will create an array of random Strings (that you will then sort). Use lengths 5, 10, 20, 40, 80.

  • Keep track of how many comparisons are necessary for each method. You could use a global counter or another method of your choice.

  • Now you should have a set of points (n,runtime(n)) for each method. Plot them using any software you like (including an online tool like this one). Which method did better? In your reflection, discuss your approach and conclusions. Include a plot of your results called plot.png.

To Submit

As a reminder, please be sure that all files are named exactly as described. Make sure you are using correct Javadoc comments for all fields and methods (and regular comments within methods). Include your name (@author field) and date (@version field) for each file. Starting from Homework 3 I will be evaluating on style.

  • readme.txt, containing your reflections on this assignment. How are you feeling about Java? What techniques have you mastered? What is still difficult? How did this homework go relative to the last few homeworks? How was pair programming this time?

  • SortingApp.java

  • LinkedList.java

  • Node.java

  • typescript, this time showing all the output of all your sorting algorithms. Try to keep this comprehensive but brief.

  • plot.png, a plot showing the runtime of your two sorting algorithms.

Extra Credit

(very small amount) Implement cocktail sort (bubble sort going back and forth, instead of always starting at the beginning) and assess its runtime in a similar manner, adding it to your graph.