0. Introduction. For this project, you will implement a highly efficient algorit

ID: 3822689 • Letter: 0

Question

0. Introduction.

For this project, you will implement a highly efficient algorithm to sort singly linked linear lists of integers. (We’ll discuss algorithms to sort arrays later in the course.) The project will give you 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 last 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 as we visit them 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 first 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 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 much more efficient. It works without exchanging adjacent integers, and without traversing lists repeatedly, both of which can make a sorting algorithm slow. Our sorting algorithm needs only O(n log n) comparisons to sort a list of n integers. The algorithm works in four phases: first testing, next halving, then sorting, and finally merging. 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 unsortedbecomes empty.

STEP

left

right

unsorted

[]

[5, 8, 4, 9, 1, 2, 3, 7, 6]

[5]

[]

[8, 4, 9, 1, 2, 3, 7, 6]

[5]

[8]

[4, 9, 1, 2, 3, 7, 6]

[4, 5]

[8]

[9, 1, 2, 3, 7, 6]

[4, 5]

[9, 8]

[1, 2, 3, 7, 6]

[1, 4, 5]

[9, 8]

[2, 3, 7, 6]

[1, 4, 5]

[2, 9, 8]

[3, 7, 6]

[3, 1, 4, 5]

[2, 9, 8]

[7, 6]

[3, 1, 4, 5]

[7, 2, 9, 8]

[6]

[6, 3, 1, 4, 5]

[7, 2, 9, 8]

[]

We did the halving phase like this 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 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 always shorter than the original list unsorted. That means left and rightwill eventually have exactly one integer, stopping the algorithm during the testing phase.

Merging. Here we merge the sorted left and right into one sorted list, called merged, 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 merged (as in step 01). If the integer from right is smallest, then we delete it and add it to the end of merged (as in step 02). If both integers are equal, then we do this to either one. We continue in this way until left or right become empty (as in step 07).

STEP

merged

left

right

[]

[1, 3, 4, 5, 6]

[2, 7, 8, 9]

[1]

[3, 4, 5, 6]

[2, 7, 8, 9]

[1, 2]

[3, 4, 5, 6]

[7, 8, 9]

[1, 2, 3]

[4, 5, 6]

[7, 8, 9]

[1, 2, 3, 4]

[5, 6]

[7, 8, 9]

[1, 2, 3, 4, 5]

[6]

[7, 8, 9]

[1, 2, 3, 4, 5, 6]

[]

[7, 8, 9]

At this point, either left and right may not be empty (step 07). If that happens, then we add the entire nonempty list to the end of merged. 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 merging 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 leftor right to the end of merged at the end.

For this project, you must implement this sorting algorithm in Java. The next section explains how to implement it efficiently.

2. Implementation.

The file SortyList.java is available obelow. It contains Java source code for the class SortyList, which implements a singly linked linear list of int’s that can be sorted. (Unlike most classes from the lectures, SortyList doesn’t need a class parameter like <Base>.) You must write a sorting method for SortyList. The class SortyList has the following members.

private 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 key, and a Node slot called next, which points to the next Node in the list, or to null. It also has a constructor that initializes key and next.

public SortyList()

Constructor. It makes an empty instance of SortyList, with no Node’s.

public SortyList(int first, int ... rest)

Constructor. It makes an instance of SortyList with one or more Node’s. The int in the first Node is first. The remaining Node’s have int’s from the array rest. This constructor uses Java syntax that was not discussed in the lectures. Don’t worry: you don’t have to know how it works.

private Node head

A head Node, made by SortyList’s constructor.

public SortyList sort()

Sort the int’s in this instance of SortyList, by calling the private sort method. Return the sorted instance.

private Node sort(Node unsorted)

THIS IS THE ONLY METHOD YOU MUST WRITE. It takes a linear linked list called unsorted as its argument, sorts the list according to its key slots, and returns the list after it’s sorted. See below for more about how sort must work.

public String toString()

Return a string that allows printing this instance of SortyList.

public static void main(String[] args)

Make some instances of SortyList, sort them, and print them. The tests demonstrate whether your sort method works correctly. It also has some examples of how SortyList’s constructor and its public sort method work.

As stated above, the private method sort is all you must write for this project. However, to make the sort algorithm more efficient, and to make the project harder and more interesting, your method sort 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 other classes, new arrays, etc. If you need a head node, then you must use the private variable head, made by SortyList’s constructors. That means sort must work in O(1) space, not counting the memory space used for recursion.

Since you can’t make new Node’s, your sort algorithm must work only by changing the next slots of existing Node’s. You can change the key slots of Node’s too, but you probably won’t want to do that.

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

Your testing phase must take O(1) time. That means it can’t use a loop to count how many Node’s are in unsorted. Hint: recall a question on the second midterm exam.

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 it can’t traverse left and right at all. It also can’t count how many Node’s are in unsorted, since that would require an extra traversal. Hint: recall how linked stacks work.

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

Your merging 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 merged must take O(1) time. That means the merging phase can’t traverse left and right more than once, and it can’t traverse merged at all. Hint: recall how linked stacks and linked queues work.

Your method sort must work correctly for lists of any length, and for lists other than the ones in the examples. It also must work correctly for lists with duplicate elements.

You may write additional private 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 SortyList, except its private sort 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. If you can make the algorithm work with diagrams, then you can make it work with Java code.

My implementation of sort uses about 75 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 sort should be. Your code may be shorter or longer than mine, and still be correct.

3. Deliverables.

The project is worth 40 points: the testing phase is worth 5 points, the halving phase is worth 15 points, the sorting phase is worth 5 points, and the merging phase is worth 15 points.

You must submit (1) Java source code for the class SortyList that includes your code for sort, and (2) any output produced by its main method. You must submit exactly one .java file that contains both these things. Output from main must appear in comments at the end of your file.

4. SortyList.java

STEP

left

right

unsorted

[]

[5, 8, 4, 9, 1, 2, 3, 7, 6]

[5]

[]

[8, 4, 9, 1, 2, 3, 7, 6]

[5]

[8]

[4, 9, 1, 2, 3, 7, 6]

[4, 5]

[8]

[9, 1, 2, 3, 7, 6]

[4, 5]

[9, 8]

[1, 2, 3, 7, 6]

[1, 4, 5]

[9, 8]

[2, 3, 7, 6]

[1, 4, 5]

[2, 9, 8]

[3, 7, 6]

[3, 1, 4, 5]

[2, 9, 8]

[7, 6]

[3, 1, 4, 5]

[7, 2, 9, 8]

[6]

[6, 3, 1, 4, 5]

[7, 2, 9, 8]

[]

Explanation / Answer

HI, I have implemented the required methods.

Please let me know in case of any issue.

//SORTY LIST. A linked list of INT's that can be efficiently sorted.

public class SortyList

{

//NODE. A node in a singly linked linear list of INT's.

private class Node

{

private int key; // The INT.

private Node next; // The next NODE in the list, or NULL.

//Constructor. Make a NODE with KEY and NEXT.

private Node(int key, Node next)

{

this.key = key;

this.next = next;

}

private Node head; // Head NODE.

private Node first; // First NODE in a list of NODEs.

//SORTY LIST. Constructor. Make a list of NODEs that holds the INT arguments.

//Also make a HEAD node for SORT to use.

public SortyList()

{

head = new Node(0, null);

}

public SortyList(int first, int ... rest)

{

Node last = new Node(first, null);

this.first = last;

for (int index = 0; index < rest.length; index += 1)

{

last.next = new Node(rest[index], null);

last = last.next;

}

head = new Node(0, null);

}

//SORT. Sort the list whose first NODE is FIRST. We can't make more NODEs but

//we can change the NEXT slots of the existing NODEs.

public SortyList sort()

{

first = sort(first);

return this;

}

//Sort the list UNSORTED without making any new NODE's, and return the sorted

//list.

private Node sort(Node unsorted)

{

//YOUR CODE GOES HERE!

/* Base case -- length 0 or 1 */

if(unsorted == null || unsorted.next == null){

return unsorted;

}

//get middle node for Split head into 'a' and 'b' sublists

Node mid = getMidNode(unsorted);

Node a = unsorted;//firstList

Node b = mid.next;//secondList

mid.next = null;

/* Recursively sort the sublists */

sort(a);

sort(b);

/* answer = merge the two sorted lists together */

unsorted = SortedMerge(a,b);

return unsorted;

}

private Node getMidNode(Node head){

Node slow = head;

Node fast = head.next;

while(fast != null && fast.next != null){

slow =slow.next;

fast =fast.next.next;

}

return slow;

}

private Node SortedMerge(Node a,Node b){

Node result = null;

/* Base cases */

if (a == null)

return(b);

else if (b==null)

return(a);

/* Pick either a or b, and recur */

if (a.key <= b.key) {

result = a;

result.next = SortedMerge(a.next, b);

}

else{

result = b;

result.next = SortedMerge(a, b.next);

}

return(result);

}

//TO STRING. Turn FIRST into a string for printing. If the list is empty then

//the string is "[]". Otherwise it's "[K, K ..., K]" where the K's are the

//KEYS from FIRST, in order of appearance.

public String toString()

{

StringBuilder builder = new StringBuilder();

builder.append('[');

if (first != null)

{

Node temp = first;

builder.append(temp.key);

temp = temp.next;

while (temp != null)

{

builder.append(", ");

builder.append(temp.key);

temp = temp.next;

}

builder.append(']');

return builder.toString();

}

//MAIN. Test SORTY LIST by running it on a few examples.

public static void main(String[] args)

{

System.out.println(new SortyList() .sort());

System.out.println(new SortyList(0) .sort());

System.out.println(new SortyList(1, 0) .sort());

System.out.println(new SortyList(2, 1, 0) .sort());

System.out.println(new SortyList(9, 8, 7, 6, 5, 4, 3, 2, 1, 0).sort());

System.out.println(new SortyList(5, 8, 4, 9, 0, 1, 2, 3, 7, 6).sort());

}

Sample run:

[]

[0]

[0, 1]

[0, 2]

[4, 9]

[1, 2, 3, 5, 7, 8, 9]

Navigate

0. Introduction. For this project, you will implement a highly efficient algorit

0. Introduction. In our culture, we claim to believe that everyone has equal ran

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

0. Introduction. For this project, you will implement a highly efficient algorit

Question

Explanation / Answer

Related Questions

Navigate