We’ll write something like [5, 8, 4, 9, 1, 2, 3, 7, 6] to mean such a list. This

Question

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 unsorted becomes empty.

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 right will 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).

class SortyList is given below, only need to write the function, private Node sort(Node unsorted), with the testing, halving, sorting, and merging phases.

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 bySortyList’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.

Explanation / Answer

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 merge(Node a, Node b)
{
      Node temp=head;
      while(a!=null && b!=null)
      {
        if(a.key<=b.key)
        {
          temp.next=a;
          temp=a;
          a=a.next;
        }
        else
        {
          temp.next=b;
          temp=b;
          b=b.next;
        }
      }
      temp.next= (a==null)? b:a;
      return head.next;
}
private Node sort(Node unsorted)
{
      if(unsorted==null||unsorted.next==null)
        return unsorted;
      Node a=unsorted;
      Node b= unsorted.next;
      while(b!=null && b.next!=null)
      {
        unsorted=unsorted.next;
        b=(b.next).next;
      }
      b=unsorted.next;
      unsorted.next=null;
      return merge(sort(a),sort(b));
// YOUR CODE GOES HERE!
}

// 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());
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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