Order-related manipulations

Sorted is a promise about a whole collection: walk it from the front and no value ever turns up before a value that belonged earlier. Nothing in Java enforces that promise. It holds because every method that changes the collection keeps it, and it stops holding the first time one of them does not. Three methods live around that promise. addOrdered keeps it while values arrive, a sort restores it, and a search spends it.

What "earlier" means, before any code

You cannot sort values you cannot compare, and Java will not guess how. For a primitive, < and > are built in. For an object, comparing is a method call, and the method is compareTo.

int sign = a.compareTo(b);

Read what comes back as a sign and nothing else. Negative means a comes before b. Zero means they tie. Positive means a comes after. The size of the number is not part of the contract, so the only comparisons to write are against 0.

if (a.compareTo(b) < 0)    // a comes first
if (a.compareTo(b) == 0)   // they tie
if (a.compareTo(b) > 0)    // b comes first

Every ordering method below that works on objects is built out of that one call, which is why a class has to implement Comparable before any of them can touch it. Writing that method belongs to the data abstraction area, worked in Implementing Comparable on a Student class. This page assumes a class already has it and uses what it returns.

addOrdered: never let it get out of order

Adding at the front is easy because you already know which node the new one attaches to. Adding in sorted position is a different problem, because the right spot depends on the value itself, and you do not know where it is until you go looking. addOrdered goes looking, one comparison at a time, and stops the instant it finds the spot.

public void addOrdered(E item)
{
    Node fresh = new Node(item);
    Node prev = null;
    Node cur = this.head;
    while (cur != null && cur.data.compareTo(item) < 0)
    {
        prev = cur;
        cur = cur.next;
    }
    fresh.next = cur;             // aim before you break
    if (prev == null)
    {
        this.head = fresh;        // the front, or the list was empty
    }
    else
    {
        prev.next = fresh;        // splice
    }
    this.size++;
}

Two cursors move together. cur does the looking, walking forward while the node it is standing on still holds a value smaller than the one you are inserting. prev trails one node behind it the whole way, because when cur stops, prev is the node whose next has to change.

The order inside the loop test is a safety rule. Java checks cur != null first, and only runs cur.data.compareTo(item) if that was true. Write the halves the other way round and a walk that reaches the end of the list calls compareTo on nothing and dies. Checking cur first, every time, is what keeps the second half safe.

The loop stops on the first node the new value does not belong in front of. Either half can end it: cur ran off the end, or the node cur is on is no longer smaller. Both leave the cursors exactly where the wiring needs them.

The comparison is strict. < 0, not <= 0. A value equal to the one you are inserting does not count as smaller, so the loop stops on it rather than walking past, and the new value lands immediately in front of the equal one already there. The list is sorted either way, so nothing breaks. It is worth knowing which way it goes so the output does not surprise you.

One branch covers 2 situations. prev starts as null and the only line that changes it is inside the loop, so prev is still null exactly when the loop body never ran: the list was empty, or the new value belongs in front of everything. Both want the same fix, which is that the new node becomes the head, and if (prev == null) is the one test both satisfy. On a list that keeps a sentinel node at the front, prev starts on the sentinel instead of on null, so that branch disappears completely.

Trace it 4 times from empty and the whole method is in front of you.

Call it once for every value in an unsorted pile and the list you end up with is sorted. That is insertion sort, the same algorithm you have seen on an array, written as pointer edits on a chain instead of shifts inside an array. It costs what insertion sort costs, because every call still has to walk to find its spot.

A sort you can write from memory

One sort is enough, and selection sort is the one to have cold, because you can reconstruct it from a sentence: find the smallest value that is not yet placed, put it in the next position, repeat. It works the same on an array and on a chain of nodes. The only thing that changes is what a swap reaches into.

On an array a swap trades 2 slots. A linked list has no slots. It has nodes joined by next references, each carrying its value in a data field. The tempting move is to move the node: unhook the one holding the smallest value and hook it in at the front instead. That is real surgery. You would touch the node before it, the node after it, the node currently in front, and possibly head, and you would need separate branches for the smallest value already being in front and for it sitting right next to the front.

None of that is necessary, because you do not need the smallest value's node in front. You need its value there. So find the node holding the smallest remaining value and trade the 2 data fields. Draw the list before and after and every arrow lands in the same place. Only the contents of 2 boxes changed.

before:  4 -> 9 -> 1 -> 6
after:   1 -> 9 -> 4 -> 6
         ^         ^
         the only 2 things that changed

Here is the algorithm on an int array, where a swap trades 2 slots.

public static void sort(int[] array)
{
    for (int i = 0; i < array.length; i++)
    {
        int min = i;
        for (int j = i + 1; j < array.length; j++)
        {
            if (array[j] < array[min])
            {
                min = j;
            }
        }
        if (min != i)
        {
            int temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
    }
}

Two loops, nested, with 2 different jobs. The outer one marks the position about to be filled and steps forward one index at a time. The inner one hunts from the very next index onward for the smallest value not yet placed. min starts equal to i, which is a way of saying nothing has beaten this one yet, and it only moves when j finds a smaller value.

Follow 4 slots through every pass and the whole thing is visible. Only values are shown, because only values move.

Two small rules separate a correct selection sort from one that passes the easy cases.

The comparison is strict: <, never <=. Equal values already tie, and swapping values that tie changes nothing about how the array reads. Writing <= tells the inner loop to move min onto a slot that is not smaller, and the swap that follows trades 2 values that were already in a fine order. On an array full of duplicates that is a swap per pass doing nothing.

Guard the swap with min != i. When the outer position already holds the smallest remaining value, the inner loop finds nothing better and min never moves. Swapping a slot with itself through a temporary reads one slot, writes it straight back, and writes the same value a second time. Three operations that accomplish nothing, on every pass where the array was already in order at that position.

Empty, one, many, as always. An empty array has a length of 0, the outer test fails immediately, and sort returns having touched nothing, which is correct. An array of 1 runs the outer loop once, the inner loop starts at index 1, which is already past the end, so it never runs, min is still i, and the guard skips the swap.

Search: linear on anything, halving only on an array

Searching is the reason to keep things in order, and the 2 kinds of search want 2 different things from you.

A linear search looks at values from the front until it finds a match or runs out. It needs nothing: no order, no ability to jump. It works on an array and on a chain, and on a chain it is the only kind available.

public int indexOf(Object target)
{
    int index = 0;
    Node cur = this.head;
    while (cur != null)
    {
        if (cur.data.equals(target))
        {
            return index;
        }
        cur = cur.next;
        index++;
    }
    return -1;
}

Three things in there are the whole pattern. The comparison is equals, not ==, because == on objects asks whether 2 references point at the same object and reads no fields at all. The loop test is cur != null, the one that visits every node including the last, because a search has to be able to run out. And there has to be an answer for not found, which by convention is -1 for an index and null for an object, chosen because no real index is negative.

A binary search throws away half the remaining range on every comparison, the way you find a word in a dictionary. It needs 2 things a linear search does not: the values in order, and the ability to jump straight to the middle one. An array gives you both, and Arrays.binarySearch is written for exactly that. A chain of nodes gives you only the order, because reaching the middle node means walking to it, and walking to the middle costs as much as the linear search you were trying to avoid.

On an array, sorting first can pay for itself many times over. On a linked list, sorting buys you ordered output and a slightly earlier stop when you are looking for something that is not there, and it does not buy you a faster lookup.

What "grossly inefficient" points at

This is the one area where the official topic list attaches a penalty, and it is worth reading the sentence as written.

Penalty points can be assessed in this category for grossly inefficient code

Official site: FAQs About the APE, item 15.

Grossly inefficient, not merely slow. Nobody is counting instructions or asking you to pick the theoretically best algorithm. The word points at a program doing the same work repeatedly for no reason, and in this material it takes a small number of recognizable shapes.

The check that catches all 5 takes 30 seconds. After you write a method, count how many times it looks at each value, and ask what the job actually required. Selection sort looks at each value about once per pass and there are as many passes as values, and that is the algorithm working as designed. A single walk that turns into 2 nested walks for an answer one walk could have produced is the other thing.

In the practice APE

The Practice APE Exam Instructions put one ordering problem in this area: a sort method on a linked list that keeps a sentinel node at the front. The class is given to you complete except for that one method, and reading what is given is most of the work.

private class Node
{
    private Comparable data;
    private Node next;
    // constructors
}

private Node head;
private int size;

public LinkedListDummySort()
{
    this.head = new Node(null, null);
    this.size = 0;
}

public void addFirst(Comparable data)
{
    this.head.next = new Node(data, this.head.next);
    this.size++;
}

public void sort()
{
    // yours
}

Four facts are sitting in that code, and each one decides something about the method you write.

The constructor builds a node before anything is added, so head is never null and the first real value is in head.next. An empty list is head.next == null. A walk that starts at head starts on a node holding nothing.

The field is declared Comparable, not a type parameter, so data.compareTo(other.data) is how 2 values compare and the temporary in your swap is a Comparable.

addFirst puts each value in front of the last one, so a list built by calling it reads back in the reverse of the order it was built. That is why the test that adds first then second starts out as second first and needs a real swap, while the one that adds second then first is already sorted.

toString prints the size on its own first line and then one value per line. Perfect ordering with a stale size is still wrong output, and a sort does not change the size at all.

The file also carries its own rule for this problem, in its own words: you must write the algorithm to sort, and no calls to sort methods that are part of the Java API are allowed. So Collections.sort and Arrays.sort are not available here, which is the reason to have one sort you can write from a blank file. Copying the values out into an ArrayList, sorting that, and writing them back is the same call with extra steps, so it breaks the same rule. The rule names no algorithm, so which sort you write is up to you. Selection sort swaps values rather than rewiring nodes.

The case worth checking your work against is the 10-value one. Adding these with addFirst, in this order, gives a list in no particular order:

apple, cherry, persimmon, orange, tomato,
kumquat, lemon, grape, lime, banana

And after sort(), what toString prints:

List size is: 10
apple
banana
cherry
grape
kumquat
lemon
lime
orange
persimmon
tomato

Strings compare alphabetically, because String already implements Comparable and its compareTo works character by character. There is nothing to write for that part.

Readiness check

Work each one on paper and write the answer down before you open it.

The one thing to keep

Order is a promise every method has to keep, and compareTo read as a sign is the only tool that decides what "earlier" means. addOrdered walks while the node in front is still smaller, with prev trailing, checks cur != null first, and wires the new node forward before it breaks the old arrow. Selection sort scans for the smallest value not yet placed and swaps the data, never a link, with a strict comparison so ties do not move and a min != i guard so a position never swaps with itself. Search with equals, visit every node with the cur != null test, and have an answer for not found. Then count the passes, because a second walk inside the first one is what the penalty sentence is about.