Course Links

Exercises

Resources

External

Your task on this assignment is to put together what you know about linked lists with what have learned about sorting algorithms. Your text has detailed implementations of many sorting algorithms for arrays, and similar resources can be found on the web. As you know, nearly anything that can be done using arrays can also be done using linked lists -- sometimes more easily, sometimes less so. You will demonstrate the truth of this by implementing sorting algorithms based on linked lists instead of arrays. (Note that due to their differing strengths and weaknesses you will probably not want to follow an array-based implementation too closely; just keep the fundamental spirit intact.)

For this assignment, you will implement two of three sorting algorithms using linked lists: you must implement merge sort, plus one of either insertion sort or selection sort at minimum. For a top grade you should do all three. A detailed analysis and implementation of these algorithms using arrays appears in your textbook; you may refer to these as you develop your list implementation. But try to avoid the use of any methods that involve traversal across the list, including index-based methods and also ones that require searching for a particular element.

Sorting algorithms vary in their efficiency, particularly for longer lists. In the final part of this assignment, you will test your implementions on lists of varying lengths, to see how the sorting time changes.

You may work alone on this assignment, or you may decide to work in a pair under two conditions: (1) you choose a partner you have not previously worked with before, and (2) both partners are present at all programming sessions -- one partner may not work alone and then meet with the other to "catch them up".

Program Specifications

Your programs should follow the outline given in CardSortDemo: initialize a deck of cards, shuffle them, and then sort them. As it sorts, the program should create a record of what it does using the SortRecorder class, as shown in the demo. You should create one snapshot per outer loop iteration in insertion sort and/or selection sort, and one snapshot per merge operation in merge sort.

Write separate programs for each sorting algorithm you implement. They should be called CardInSort.java CardSelSort.java, and CardMergeSort.java, respectively.

Sorting with Linked Lists

You may use the CardPile class, which is based upon LinkedList<Card>. Note that the demo program begins by creating a full deck and then shuffling it randomly. Your program should perform all processing on the linked list structure, using iterators where necessary to keep track of position in the list. For top marks, avoid using an index to refer to an element of the list -- indices are efficient for arrays, but not for lists. Similarly, you should avoid calling methods that trigger a hidden traversal of the list, such as get.

Processing a list differs in style from processing an array. Insertion and deletion of elements is easy on a list, but hard in an array (because a full array includes no room for insertion, and deletion leaves an empty hole in an otherwise full array). The algorithms we developed for sorting on arrays involved lots of swapping, because the only way to make room for an element was to move another one out of the way. With lists, instead of swapping two elements, you will tend instead to work with two lists, excising elements from the unsorted list and inserting them into the sorted list without disturbing any other nodes. If you find yourself swapping values using set(), you're probably using the lists too much like arrays, and failing to take advantage of their strengths. Note that the unsorted list will begin full and shrink as elements are removed from it, while the sorted list will begin empty and grow until it contains all the elements of the original unsorted list. Below are summaries of selection sort and insertion sort as implemented on linked lists.

Selection Sort:
Until unsorted is empty, scan it for the smallest remaining element. Remove that element from unsorted and add it to the tail of sorted. (One way to do this: Loop through all the nodes, keeping the index of the smallest element seen so far as you continue to scan through the list, then remove that element by index. Another way: avoid using an index by actually pulling out the smallest element seen so far, and then swapping it back in if and when you encounter a smaller one. Yet another: use two iterators, one to traverse the loop element by element and the other to hold the place of the smallest element seen so far, so you get a stable sort.)
Insertion Sort:
Until unsorted is empty, take the first element off it and find the point where it should go in sorted (the point where all previous elements are smaller, and all following elements are equal to or greater than). Insert it into sorted at this point.

Merge Sort

Your other program will implement Merge Sort, another algorithm for sorting. It is much easier to implement using lists, rather than arrays. A high-level description of the algorithm is given below.

Input:
A list A of cards, of length n.
Output:
A new list of the same cards in increasing order.
Algorithm:
Begin by placing each element of A into a new singleton list. You may store all the singleton lists in a list of lists (or superlist).

While more than one list remains, take the first two lists from the superlist and merge them, preserving the sorted order. Put the result back at the end of the superlist.

To merge two sorted lists into a single sorted list, look at the first element in each list. Take the smaller of the two off the front of its old list and put it at the end of the new (merged) list. Repeat this until both one of the old lists is empty, at which point you can append the remainder of the other original list to the new list. If the original lists were sorted, and you always take the smallest element available, then the resulting list will also be sorted. (You might want to convince yourself of this fact before continuing.)

Note that the key operation here is the merging of two sorted lists. Probably you will want to develop a method for this and test it thoroughly before tackling the full program.

Experimentation

You now have an opportunity to do some empirical investigation of differences in their running time. Once your programs are written, and thoroughly debugged, you can make a variant version that doesn't contain any reference to SortRecorder, following this demo: TimerDemo.java. (Eliminating the recording is necessary because recording takes up both time and memory, which gets in the way of measuring the time required for the sorting itself. Make sure you disable any debugging printouts as well.) Call the variant versions InSortTiming, SelSortTiming, and MergeSortTiming, respectively. You will use these stripped-down versions to sort large CardPiles of different sizes, as described below, so that you can see for yourself how they compare for speed. The conclusions you draw should be written up in your readme.txt file.

You can time a program on unix systems by preceding the call to run it with time. For example:

time java MergeSortTimer 10000

This will print out a rather cryptic result, with timing numbers in different orders depending on the system. On aurora, the first number gives the time spent running the program by the CPU, which is the number you are most interested in. The second number gives the amount of time spent in system calls, and the third number gives the actual time elapsed. On some operating systems, the information provided may be somewhat different, but it you should still be able to figure out which number is the CPU time.

Please run a sort using each of your programs on inputs that double progressively in size: 10000 cards, 20000 cards, 40000 cards, etc. Continue until you see a clear difference in speed, or until one method is unable to finish in a reasonable time (say a few minutes). Then write up a short summary of your findings to include in the readme.txt. Do your experiments match your expectations?

Extra Credit

If you finish all three assigned sorting algorithms, you may pick another of your choice (anything but bubble sort) to research, implement, and add to the timing experiment. Wikipedia has detailed articles on many algorithms.

To Submit

(There is no need to include the timing classes, since they should contain the same sorting routine as in your other programs. However, you should show them running in the typescript and summarize the results in your readme.)

Quick Start