CSCI 1913: Introduction to Algorithms-Programming Project 2 Solved

Data Structures, and Program Development 

0.  Introduction.

For this project, you will implement an efficient algorithm to sort linear singly-linked lists of integers. (We’ll discuss algorithms that sort arrays later in the course.) The project is intended to give you some practice working with linked data structures.

1.  Theory.

To start, we need a notation for lists of integers. We’ll write something like [5, 8, 4, 9, 1, 2, 3, 7, 6] to mean such a list. This list has nine nodes: its first node contains a 5, its second node contains an 8, its third node contains a 4, etc., all the way to its ninth node, which contains a 6. We’ll write an empty list of integers as []. Java does not use this notation, so don’t put it in your programs.

      We want to sort lists like these into nondecreasing order. That means that the integers in the list don’t decrease from left to right. For example, if we sort [2, 3, 1, 1, 2] into nondecreasing order, then we get [1, 1, 2, 2, 3]. Similarly, if we sort [5, 8, 4, 9, 1, 2, 3, 7, 6] into nondecreasing order, then we get [1, 2, 3, 4, 5, 6, 7, 8, 9]. We’ll use this list as a running example in the rest of this description.

      We also want our sorting algorithm to be as efficient as possible. To explain what we mean by that, let’s consider an inefficient sorting algorithm. It might sort a list by traversing it, looking for pairs of adjacent integers that are in the wrong order, like 8 and 4 in the list shown above. Whenever it finds such a pair of integers, it exchanges their positions, so that 4 now comes before 8. The algorithm might repeatedly traverse the list in this way, exchanging integers until all are in the right order. Although this algorithm is simple, it needs O(n²) comparisons to sort n integers.

      The sorting algorithm we’ll describe here is more complex, but also more efficient. It works without exchanging adjacent integers, and without traversing lists repeatedly, both of which can make a sorting algorithm slow. Our algorithm needs only O(n log n) comparisons to sort a list of n integers. The algorithm works in four phases: testing, halving, sorting, and combining. We’ll describe each phase in detail.

Testing. Suppose that the variable unsorted is an unsorted list of integers that we want to sort. We test if unsorted has length 0 or 1. If so, then the list is already sorted, so the algorithm simply stops and returns unsorted as its result.

Halving. In this phase, unsorted has two or more integers. We split unsorted into two halves, called left and right, with approximately equal lengths. The order of integers within left and right doesn’t matter. We start (step 01) with left and right as empty lists. Then, for odd numbered steps (01, 03, etc.) we delete the first integer from unsorted and add it to the front of left. For even numbered steps (02, 04, etc.), we delete the first integer from unsorted and add it to the front of right instead. We continue in this way until unsorted becomes empty.

  STEP  
  left  
  right  
  unsorted  
 01
 []
 []
 [5, 8, 4, 9, 1, 2, 3, 7, 6]
 02
 [5]
 []
 [8, 4, 9, 1, 2, 3, 7, 6]
 03
 [5]
 [8]
 [4, 9, 1, 2, 3, 7, 6]
 04
 [4, 5]
 [8]
 [9, 1, 2, 3, 7, 6]
 05
 [4, 5]
 [9, 8]
 [1, 2, 3, 7, 6]
 06
 [1, 4, 5]
 [9, 8]
 [2, 3, 7, 6]
 07
 [1, 4, 5]
 [2, 9, 8]
 [3, 7, 6]
 08
 [3, 1, 4, 5]
 [2, 9, 8]
 [7, 6]
 09
 [3, 1, 4, 5]
 [7, 2, 9, 8]
 [6]
 10
 [6, 3, 1, 4, 5]
 [7, 2, 9, 8]
 []
We do the halving phase this way because it’s easy to delete an integer from the front of a linked list (as in a linked stack), and easy to add a new integer to the front of a linked list (again as in a linked stack). Also, it works without having to know the length of unsorted.

Sorting. Now we have two unsorted lists from the halving phase, left and right. In the example, left is [6, 3, 1, 4, 5], and right is [7, 2, 9, 8]. We sort left and right into nondecreasing order, by recursively using the sorting algorithm (the same one we’re describing!) on both lists. After that, left is [1, 3, 4, 5, 6], and right is [2, 7, 8, 9]. The recursion always terminates, because left and right are shorter than the original list unsorted, so they will eventually have only one integer, stopping the algorithm during its testing phase.

Combining. Here we combine left and right into one sorted list, called sorted, which is initially empty (step 01). We look at the first integers from left and right, choosing the one that’s smallest. If the integer from left is smallest, then we delete it and add it to the end of sorted (as in step 01). If the integer from right is smallest, then we delete it and add it to the end of sorted (as in step 02). If both integers are equal, then we can do either one. We continue in this way until left or right becomes empty.

 STEP  
 
 sorted  
 left  
 right  
 01
 []
 
 [1, 3, 4, 5, 6]
 [2, 7, 8, 9]
 
 
 
 
 
                                                       02       [1]                   [3, 4, 5, 6]       [2, 7, 8, 9]

 03
 [1, 2]
 [3, 4, 5, 6]
 [7, 8, 9]
 04
 [1, 2, 3]
 [4, 5, 6]
 [7, 8, 9]
 05
 [1, 2, 3, 4]
 [5, 6]
 [7, 8, 9]
 06
 [1, 2, 3, 4, 5]
 [6]
 [7, 8, 9]
 07
 [1, 2, 3, 4, 5, 6]
 []
 [7, 8, 9]
At this point, one of left and right may not be empty (step 07). If that happens, then we add the entire nonempty list to the end of sorted. In the example, we get the list [1, 2, 3, 4, 5, 6, 7, 8, 9]. It’s sorted into nondecreasing order, so we stop the sorting algorithm and return this list as its result.

      We did the combining phase this way because it’s easy to delete an integer from the front of a linked list (as in a linked stack) and also easy to add an integer to the end of a linked list (as in a linked queue). It’s also easy to add left or right to the end of sorted.

2. Implementation.

For this project, you must implement the sorting algorithm from the previous section in Java. The file tests.java is available on Canvas. It contains Java source code for the class Sort, which implements a linear singly-linked list of int’s that can be sorted. You must write a sorting method called sortNodes for Sort. The class Sort has the following members, all of which are static.

private static class Node

A nested class. The linked lists that you must sort are made from instances of Node. Each instance of Node has an int slot called number. It also has a Node slot called next, which points to the next Node in the list, or to null. And it has a constructor that initializes the number and next slots.

private static Node makeNodes(int ... numbers)

This method takes a series of int’s as its arguments. It constructs a linear singly-linked list of Nodes that contains those int’s, then returns it. (It also uses Java syntax that was not discussed in the lectures—but you don’t have to know how it works.)

private static Node sortNodes(Nodes unsorted)

THIS IS THE ONLY METHOD THAT YOU MUST WRITE. It takes a linear singly-linked list of Nodes called unsorted as its argument, sorts the list in nondecreasing order of its number slots, and returns the sorted list.

private static void writeNodes(Node nodes)

This method writes the int’s in nodes, a linear singly-linked list of Node’s, separated by commas and surrounded by square brackets.

public static void main(String[] args)

Test the method sortNodes by making a few linear singly-linked lists of Node’s, sorting them, and writing them.

As stated above, the method sortNodes is all you must write for this project. However, to make the sort algorithm more efficient, and to make the project more interesting, sortNodes must follow all of these scary helpful rules:

 You must not use the Java operator new in any way! You are not allowed to make new Node’s, new instances of classes, new arrays, etc. That means sortNodes must work in O(1) space, not counting the memory used for recursion.

Since you can’t make new Node’s, sortNodes must work only by changing the next slots of existing Node’s. You are not allowed to change the number slots of Node’s.

You must use the algorithm described above in the theory section, with its four phases: testing, halving, sorting, and combining. To simplify grading, you must use the same local variable names: left, right, sorted, and unsorted. If you need more local variables, then they can have any names you want.

 Your testing phase must not use a loop to count how many Node’s are in unsorted. It must work in O(1) time.

Your halving phase must take O(u) time, where u is the length of unsorted. Adding a Node to left or right must take O(1) time. That means the halving phase can’t traverse unsorted more than once, and can’t traverse left and right at all. It also can’t count how many Node’s are in unsorted. Hint: recall how linked stacks work.

 Your sorting phase must call sortNodes recursively to sort left and right.

Your combining phase must take O(l + r) time, where l is the length of left, and r is the length of right. Adding a Node to sorted must take O(1) time. That means the combining phase can’t traverse left and right more than once, and it can’t traverse sorted at all. Hint: recall how linked stacks and linked queues work.

  Your method sortNodes must work correctly for lists of any length. It must work for lists other than those in main. In particular, it must work correctly for the empty list, and it must work correctly for lists with duplicate elements.

 You may write additional private static helper methods, but they must also follow these rules. Your helper methods can have any names you want.

You can’t change any part of the class Sort, except its sortNodes method. But main is an exception to this rule: you can add more tests to show how your code works. Also, main is the only method that is allowed to print things.

If your code violates these rules, then you will lose a large number of points. As a result, if you have questions about whether you’re following the rules correctly, then you should contact me or the TA’s. Here are more hints:

  Draw box-and-arrow diagrams! It helps to use a whiteboard. There are whiteboards available for student use in Bruininks Hall and elsewhere on campus. If you can make the algorithm work with box-and-arrow diagrams, then you can make it work with Java code.

  My implementation of sortNodes uses about 80 lines of Java code, not using helper functions, not counting comments, and indenting as I do in the lectures. This should give you a very rough idea of how complex sortNodes should be. Your code may be shorter or longer than mine, and still be correct.