Table of Contents

This is the second in a series of three posts detailing the Hilbert Sort problem, its solution, and its implementation. This post solves the problem.

• Hilbert Sort Problem
• Space Is The Place
• The Reflections
  • Reflected Quadrants
  • Scaling
  • Reflection
• Solving the Reflection Problem
• Procedure
• References

Hilbert Sort Problem

In the prior post, we covered the Hilbert Sort problem, but we state it once more succinctly here before detailing a solution to the problem.

The Hilbert Sort problem asks the following: given a set of labeled \((x,y)\) points, how can we sort the points according to the order in which they are visited by a space-filling Hilbert curve?

Revisiting the example input and output provided, the input provides the number of points and size of the grid on the first line, followed by each point's coordinates and label.

Input:
    14 25
    5 5 Honolulu
    5 10 PugetSound
    5 20 Victoria
    10 5 Berkeley
    10 10 Portland
    10 15 Seattle
    10 20 Vancouver
    15 5 LasVegas
    15 10 Sacramento
    15 15 Kelowna
    15 20 PrinceGeorge
    20 5 Phoenix
    20 10 SaltLakeCity
    20 20 Calgary

Output:
    Honolulu
    Berkeley
    Portland
    PugetSound
    Victoria
    Vancouver
    Seattle
    Kelowna
    PrinceGeorge
    Calgary
    SaltLakeCity
    Sacramento
    LasVegas
    Phoenix

Space is the Place

To solve the Hilbert Sort problem, we have to avoid the temptation to think about the Hilbert curve and the way that it is constructed. While we spent quite a bit of time talking about the Hilbert curve and how it is constructed, the curve itself is not what we are interested in - we are interested in the order in which the points are visited.

Also remember, the motivation of solving the Hilbert Sort problem is to arrange spatial \((x,y)\) points so closer points are nearer together.

No matter how many iterations of the Hilbert curve we end up drawing, we always apply the same procedure: cut the square into four quadrants, reflect the southwest corner about the bottom left to top right diagonal, and reflect the southeast corner about the bottom right to top left diagonal.

We will always visit points in the southwest quadrant before we visit points in the northwest quadrant; we will always visit points in the northwest corner before we visit points in the northeast corner; etc.

The Reflections

The trickiest part of the Hilbert Sort problem is the reflection that happens to the lower left and lower right quadrants.

Reflected Quadrants

Start with the first step of the Hilbert sort - take a square with points contained in it. Split the square into four quadrants (with the intention of creating four sub-problems). However, to conform to the Hilbert Curve construction process, the lower left and lower right squares must be reflected. The lower left square is reflected about the bottom left to upper right diagonal, while the lower right square is reflected about the bottom right to upper left diagonal.

Convince yourself of this by studying the curve construction procedure as illustrated by Hilbert himself in his 1890 paper (a.k.a., Hilbert Illustrates A Hilbert Curve):

We are working toward a recursive method - and recursive methods call themselves repeatedly, apply to subproblems that are trivially similar. However, to translate this into a recursive problem, we have to deal with the rotations within the current recursive step, in such a way that we don't need to know the orientation of the prior square to know the order in which to visit the squares - it is always southwest, northwest, notheast, southwest.

After we split the squares into quadrants, after we toss out any quadrants with no points, we walk through each of the four quadrants in order (southwest, northwest, northeast, southwest). If there is a single point in the quadrant, we add it to the priority queue.

It is here that we take care of the rotation - before we recursively call the Hilbert sort method on the quadrant itself.

Scaling

We have a prescribed order for the four quadrants in the current recursive level, and the current recursive level is working its way through each of those four quadrants. But remember, our algorithm only cares about the order of points. It does not care about the \((x,y)\) location. So we can ireflect \((x,y)\) points by changing their \((x,y)\) coordinate locations. Ultimately we are only changing the program's internal representation of each point, not the original data on disk, so we can think of \((x,y)\) as mutable for our purposes.

This is an important part of our solution: scaling (and reflecting) each quadrant before recursively calling the Hilbert sort method on the points contained in it.

If we are considering a single quadrant of dimensions \(\frac{S}{2} \times \frac{S}{2}\), containing points \((x,y)\), we may be able to pass in the corners of our square, plus the \((x,y)\) points contained in it. However, as our squares get smaller, the distance between points gets smaller as well, so this has an upper limit as to how many points it can sort.

On the other hand, we can avoid passing all that information around and using doubles, by just rescaling everything to the given quadrant. We want each recursive level to completely forget about where in the recursive stack it is, how large its square is relative to the original, etc. All it should be doing is solving the same problem repeatedly - which is what recursion is best at. If we double the sides of the square, we get a shape with original size \(S \times S\). To keep the points shifted correctly we double their \((x,y)\) coordinates to \((2x, 2y)\).

Once this transformation is performed, we are ready to call the Hilbert Sort function recursively - for the northwest and northeast quadrants only. The southwest and southeast quadrants still have a ways to go.

Reflection

In addition to the scale-up transformation, southwest and southeast qaudrant points must be reflected about their diagonals.

Here's an example of what the process looks like in action:

Solving the Reflection Problem

The above section described where in the process the reflection of the \((x,y)\) points should happen. The process of applying the reflection differs between the southwest and southeast quadrants.

In the southwest quadrant, points are being reflected about the diagonal line \(y=x\), so the reflection of \((x,y)\) points in the southwest quadrant can be performed by swapping the \(x\) and \(y\) values of all of the points in that quadrant.

In the southeast quadrant, the points are refelected about the diagonal \(y = -x\), but it is not quite \(y = -x\), given that there is an offset of a half-quadrant width on the left.

After an \((x,y)\) point is transformed, it has a height equal to the distance from the point's x coordinate to the start of the qudarant. In equations,

Further, after an \((x,y)\) point is transformed, the distance from the top of the bounding box to the former y coordinate is the new x coordinate,

The relative x coordinates of each point (relative meaning, 0 starts at the beginning of the curent square, rather than the whole square) are the x coordinates minus the half-quadrant width.

Once these reflections are performed, we pass the resulting \((x,y)\) points on to a new Hilbert sort. The new Hilbert sort will be operating on an \(S x S\) square, as before. Importantly, the \((x,y)\) points have been transformed in such a way that the order in which the Hilbert curve visits each point has not been affected.

Hilbert Sort Procedure

The implementation strategy is, obviously, recursive. What we want to do at each level is: * Start with a square and points contained in the square. * Cut the square under consideration into four quadrants. * Apply a transformation to each square so that it is re-oriented in a manner that matches our original Hilbert curve.

Once each of those squares goes through all of its respective recursive calls, it will return a sorted list of points. Then we will know what to do - we collect each of the sorted points from each of the four quadrants in order, maintain that order, and return those sorted quadrants.

To nail down the details, treat the square under consideration as ranging from \((0,0)\) to \((S,S)\).

Each time we cut a square into quadrants, we re-orient ourselves as to where \((0,0)\) is located and which quadrants will be visited in which order. If we are in the lower left quadrant, \(x\) is below \(\frac{S}{2}\) and \(y\) is below \(\frac{S}{2}\), so we rotate and reflect by swapping x and y:

        X -> Y
        Y -> X

If we are in the upper left quadrant, x is below \(\frac{S}{2}\), y is above \(\frac{S}{2}\), so subtract \(\frac{S}{2}\) from y and we're done.

        X -> X
        Y -> Y-(S/2)

If we are in the upper right quadrant, x is above \(\frac{S}{2}\), y is above \(\frac{S}{2}\), so subtract \(\frac{S}{2}\) from both

        X -> X - S/2
        Y -> Y - S/2

If we are in the lower right quadrant, our x and y values are now relative to the quadrant bounding box. The distance to the top of the bounding box to the y coordinate becomes our new x coordinate, while the distance from the right of the bounding box S to the x coordinate becomes our new y coordinate:

        X -> S/2 - Y
        Y -> S - X

Recursion always requires a base case and a recursive case. Our "base case" is the simple comparison of one or no points in each of our four quadrants. If we get to this base case, we know the order in which the Hilbert Curve will visit each of those points.

If we are not at the base case, if we have a large number of points to sort, we can bin together all the points in a given quadrant, and consider the order in which those points go with an additional level of finer granularity.

Pseudocode

set square dimension S

create unsorted queue
load points into unsorted queue

create sorted queue
sorted queue = hilbert_sort( unsorted queue, square dimension )

Now here is the Hilbert sort function:

define hilbert_sort( unsorted queue, square dimension ):
    create southwest queue
    create northwest queue
    create northeast queue
    create southeast queue
    for each point:
        if in southwest:
            create new point using X -> Y, Y -> X
            add to southwest queue
        if in northwest:
            create new point using X -> 2X, Y -> 2Y - S
            add to northwest queue
        if in northeast:
            create new point using X -> 2X - S, Y -> 2Y - S
            add to northeast queue
        if in southeast:
            create new point using X -> S - 2Y, Y -> 2S - 2X
            add to southeast queue

        hilbertsort(southwest queue, square dimension)
        hilbertsort(northwest queue, square dimension)
        hilbertsort(northeast queue, square dimension)
        hilbertsort(southeast queue, square dimension)

        create new results queue
        add points from southwest into results queue
        add points from northwest into results queue
        add points from northeast into results queue
        add points from southeast into results queue
        return results queue

References

1. "ACM Pacific Region Programming Competition." Association of Computing Machinery. Accessed 19 June 2017. <http://acmicpc-pacnw.org/>

2. "Über die stetige Abbildung einer Linie auf ein Flächenstück." D. Hilbert. Mathematische Annalen 38 (1891), 459–460. (pdf)

3. "Hilbert Curve." Wikipedia: The Free Encyclopedia. Wikimedia Foundation. Edited 29 April 2017. Accessed 23 June 2017. <https://en.wikipedia.org/wiki/Hilbert_curve>

Table of Contents

This is the first in a series of three posts detailing the Hilbert Sort problem, its solution, and its implementation. This post sets up the problem.

• Hilbert Sort: Motivation
• Hilbert, Peano, and Space-Filling Curves
• Constructing a Hilbert Curve
• Performing a Hilbert Sort
• Problem Statement
• References

Hilbert Sort: Motivation

In the next few series of posts, we will cover the Hilbert Sort problem, how it works, and how to implement it.
However, before we describe the problem further, let's start with some motivation for solving this problem.

Suppose we're dealing with a very large number of independent objects on a 2D coordinate grid, each with a coordinate location \((x,y)\). (For example, a large population of particles moving in a fluid, or a large number of characters on a map in a game.)

Here is our box of particles:

Now, suppose that we have more data than can be handled by a single computer, and we want to arrange the data on different computers. However, we want to arrange the data in such a way that we preserve the spatial characteristics of the data.

If we implement a naive sort method for Cartesian points that sorts points by x coordinate value, breaking ties with the y coordinate value, we end up with points that are neighbors in space, but far away in the data container's storage (like an array). This is particularly true if there are large crowds of points in the grid.

Here is an illustration of a set of points and their resulting storage schema in an array that sorts points by x coordinate. It shows two purple particles, close by in space, but with
several green particles further away distance-wise but not with respect to the x coordinate. The spatial locality of points is not preserved in the data container, so clearly, a better method of sorting and organizing points is needed.

An alternative to this schema that yields better locality properties, but that leads to a much higher cost for sorting points, involves iterating over each point, and for each point, finding the closest points to it in space. However, this itself requires iterating over each point. This approach ends up walking over each point (the point whose nearest neighbors we are finding), and doing a second nested walk over each point (checking if a point is a nearest neighbor to this one). The overall cost of doing this is \(O(N^2)\).

It is a deceptively tricky problem: how to organize a large group of points in a way that preserves spatial locality?

But first, we'll cover the topic of space filling curves, then return to this topic.

Space Filling Curves

Mathematician Giuseppe Peano was a prolific teacher and researcher known for many things, but one of his more curious ideas is known as the Peano Curve. Peano was attempting to answer the question of whether a continuous curve could be bounded by a finite space, and he invented a counter-example: a recipe for breaking a curve into parts that can be replicated and repeated and applied to the copies as many times as desired, and always result in a continuous curve.

The way that space-filling curves in general are constructed is to create a pattern, then scale it down and repeat it, attaching subsequent scaled-down, repeated curves. Peano simply invented the first curve; there are many variations on the original space-filling curve idea (including the Hilbert Curve - more on that in a moment).

The original 1890 paper by Giuseppe Peano is entitled "Sur une courbe, qui remplit toute une aire plane", published in 1890 in Mathematische Annalen I, Issue 36. Unfortunately, it has no pictures, but here is a rendering from Wikimedia Commons:

(Link to original on Mediawiki Commons)

Now, the Peano curve was nice, but it had some mathematical properties that made it difficult to deal with. So in 1890, David Hilbert published a follow-up paper in Mathematische Annalen I Issue 38, entitled "Ueber die stetige Abbildung einer Linie auf ein Flächenstück", which slightly modified the recipe to create a curve with more elegant mathematical properties.

Also, he included pictures.

Here is the first set of figures from Hilbert's original 1890 paper:

And here is a slightly cleaner rendering of the Hilbert Curve pattern repeated six times:

(Link to original on Wikimedia Commons)

From the abstract of Hilbert's paper:

Peano has recently shown in the Mathematical Annals, 2 by an arithmetical observation, how the points of a line can be mapped continuously to the points of a surface part. The functions required for such a mapping can be produced more clearly by using the following geometrical view. Let us divide the line to be represented-about a straight line of the length 1-into four equal parts 1, 2, 3, 4, and the surface which we assume in the form of a square of the side length 1 Straight into 4 equal squares 1, 2, 3, 4 (Fig. 1). Secondly, we divide each of the partial sections 1, 2, 3, 4 again into 4 equal parts so that we obtain on the straight the 16 partial sections 1, 2, 3, ..., 16; At the same time, each of the 4 squares 1, 2, 3, 4 is divided into 4 equal squares, and the numbers 1, 2, ..., 16 are then written to the resulting 16 squares, That each successive square follows the previous one with one side (Fig. 2). If we think of this method, as shown in Fig. 3, the next step, it is easy to see how to assign a single definite point of the square to any given point of the line. It is only necessary to determine the partial stretches of the line to which the given point falls. The squares indicated by the same numbers are necessarily in one another and include a certain point of the surface piece in the boundary. This is the point assigned to the given point. The image thus found is unambiguous and continuous, and vice versa, each point of the square corresponds to one, two, or four points of the line. Moreover, it appears remarkable that, by a suitable modification of the partial lines in the squares, a clear and continuous representation can easily be found, the reversal of which is nowhere more than three-fold.
- David Hilbert, "Über die stetige Abbildung einer Linie auf ein Flächenstück", Mathematische Annalen Vol 38

Thanks to Google Translate for an incredible job.

Constructing a Hilbert Curve

To construct a Hilbert curve, you just have to follow the recipe. It doesn't matter what your square contains so far, or how many levels in you are, whether it's the first curve or the five hundredth:

1. First, take yer square.

2. Second, quadruple yer square. That means, make four copies, that all make a square.

3. Now rotate the bottom left and bottom right via diagonal reflection.

4. Fourth step is, you're done - that's you're new square!

Performing a Hilbert Sort

We will omit a proof of the statement, but given a set of unique (x,y) points, we can always construct a minimal-size Hilbert Curve that visits each point only once.

Points can be sorted, then, according to when they would be visited by said Hilbert Curve. And this ordering provides better preservation of spatial locality and structure of points when aligning them in memory, because these space-filling curves are recursive and preserve spatial locality in a top-down fashion.

For example, if we have two points in our square, one in the lower left and one in the lower right, and we are sorting them via a Hilbert Sort, we definitely know that a Hilbert curve constructed to visit both of these points will definitely visit the lower left point (the quadrant where the Hilbert curve starts) before it visits the lower right point (in the quadrant where the Hilbert curve stops).

This requires thinking about \((x,y)\) points in the box in terms of quadrants, and the order in which the Hilbert curve will visit each quadrant or region, rather than thinking in terms of the explicit Hilbert curve that will visit each particular \((x,y)\) point:

This is a subtle shift in the thinking about this problem, but it is crucial to a successful implementation of a Hilbert sort. The problem that will follow, which asks to implement the Hilbert sort, has many distracting details, including the Hilbert curve itself.

Remember, in Hilbert sort, the end goal is not the curve itself, but the sort order.

Here is how the quadrant-by-quadrant partitioning to sort elements ends up looking when applied repeatedly:

It is important to note that the two diagonal reflections happening in the corners are the trickiest part of this problem. We will cover this operation in greater detail in the solution blog post.

Problem Statement

Following is a paraphrased problem statement from the original ACM ICPC Regional Programming Competition problem statement that this problem and its solution was based on.

"If points \((x,y)\) are sorted primarily by x, breaking ties by y, then points that are adjacent in memory will have similar x coordinates but not necessarily similar y, potentially placing them far apart on the grid. To better preserve distances, we may sort the data along a continuous space-filling curve.

"We consider one such space-filling curve called the Hilbert curve...

"Given some locations of interest, you are asked to sort them according to when the Hilbert curve visits them. Note that while the curve intersects itself at infinitely many places, e.g., at \((\frac{S}{2}, \frac{S}{2})\), making S odd guarantees all integer points are visited just once."

Here is an example input file, giving a set of points on an \(M \times N\) grid:

    14 25
    5 5 Honolulu
    5 10 PugetSound
    5 20 Victoria
    10 5 Berkeley
    10 10 Portland
    10 15 Seattle
    10 20 Vancouver
    15 5 LasVegas
    15 10 Sacramento
    15 15 Kelowna
    15 20 PrinceGeorge
    20 5 Phoenix
    20 10 SaltLakeCity
    20 20 Calgary

The corresponding output can be verified intuitively, assuming the coordinates given above are accurate! Here is the output. Indeed, the order in which each city is visited is what we would expect if we drew a space-filling Hilbert curve over a map of the western United States and Canada.

    Honolulu
    Berkeley
    Portland
    PugetSound
    Victoria
    Vancouver
    Seattle
    Kelowna
    PrinceGeorge
    Calgary
    SaltLakeCity
    Sacramento
    LasVegas
    Phoenix

Now that we've used up all of our space here describing the problem, in a follow-up post we will go into greater detail about how to solve the problem conceptually, and come up with some pseudocode for a recursive method (since this is a recursive task). Then, a third post will go into greater detail about the final Java code to perform this task.

References

1. "ACM Pacific Region Programming Competition." Association of Computing Machinery. Accessed 19 June 2017. <http://acmicpc-pacnw.org/>

2. "Sur une courbe, qui remplit toute une aire plane." G. Peano. Mathematische Annalen 36 (1890), 157–160. (pdf)

3. "Über die stetige Abbildung einer Linie auf ein Flächenstück." D. Hilbert. Mathematische Annalen 38 (1891), 459–460. (pdf)

4. "Hilbert Curve." Wikipedia: The Free Encyclopedia. Wikimedia Foundation. Edited 29 April 2017. Accessed 23 June 2017. <https://en.wikipedia.org/wiki/Hilbert_curve>

5. "Peano Curve." Wikipedia: The Free Encyclopedia. Wikimedia Foundation. Edited 16 October 2016. Accessed 23 June 2017. <https://en.wikipedia.org/wiki/Peano_curve>

Table of Contents

• Problem Description
• Solution Approach
• Algorithm
• Pseudocode
• Using an Object-Oriented Approach
• Code
• References

Problem Description

Comedian John Cleese, in his memoir So Anyway..., described the social classes of his mother and father as "upper-uper-lower-middle class" and "middle-middle-middle-lower-middle class", respectively. Write a program that will sort individuals based on a labeling of their social standing by class.

The three main classes are upper, middle, and lower. Classes progress hierarchically from right to left. For example, lower-upper would come before lower-lower. There is also ordering within a class, so upper-upper is a higher class than middle-upper.

Once you have reached the lowest level of detail of one of the classes, assume that all further classes are equivalent to middle. This means upper and middle-upper are equivalent, and middle-middle-lower-middle and lower-middle are equivalent.

Input files have a line with the number of names, then one name per line, with the name, a colon, then the title. For example:

5
mom: upper upper lowre middle class
dad: middle middle lower middle class
queen_elizabeth: upper upper class
chair: lower lower class
unclebob: middle lower middle class

The proper output should be the name of each person, sorted in order according to their social status, e.g.,

queenelizabeth
mom
dad
unclebob
chair

Solution Approach

(This discusses an approach specific to Java, but a similar approach could be adopted for other languages in which comparison operators can be overloaded for objects.)

The problem lays out all of the essential components that a solution requires. This can most easily be implemented using an object and a comparator: the object represents a person, and has a field to store their name and a field to store their titles (array-like container for Strings). These objects would then implement comparators so that individuals could be compared. This functionality then allows the array to be sorted, using the built-in Collections sort function or a custom sort function.

Algorithm

The classy algorithm can be briefly described in this way: we are iterating over two lists of strings, of possibly unequal length, and comparing them right to left. We have a few very simple rules that determine whether one title comes before the other. We have a few simple rules for breaking ties.

The core of the algorithm is the comparison operation, in which we are assuming that these two things are equal, until we encounter evidence to the contrary. Briefly, the pseudocode can be expressed as follows (where we adopt the Java convention that a negative result means the first item comes before the second item):

if item1 < item2:
    return -1
else if item1 > item2: 
    return 1
else:
    # keep going

If we find a difference, we stop and return right away, but otherwise we continue, and assume the two are equal.

The problem statement tells us that if a title is missing, and the title lengths are mismatched, we should fill in with "middle". This translates into a second comparison block, in which one of the items is hard-coded as "middle", due to an empty list of titles:

if item < "middle":
    return -1
else if item > "middle"
    return 1
else:
    # keep going

Here is how these fit together: * Start by splitting the input titles, most likely strings, into lists * Iterate over each title, from right to left, and compare the titles. * When we reach the end of the shorter list, continue comparing titles right to left, filling in "middle". * If the titles are tied, break ties with name. * The algorithm should be implemented in a way that has access to both the titles and the names of the two people being compared. * In Java, we can define people objects, then we can either have People objects implement Comparable, or we can define our own Comparator for two People objects.

Pseudocode

When we translate the above procedure into Python-like pseudocode, here is the result:

define compare_lengths(title1, title2):
    list1 = title1.split()
    list2 = title2.split()
    for i in min(list1.size, list2.size):
        sal1 = list1.reverse[i]
        sal2 = list2.reverse[i]
        if sal1 < sal2:
            return -1
        else if sal1 > sal2:
            return 1

    larger_list = <point to larger list>
    for i in ( min(list1.size,list2.size)+1 ... max(list1.size, list2.size) ):
        salX = larger_list.reverse[i]
        if SalX < "middle":
            return -1
        if salX > "middle"
            return 1

    # If you get here, it's a tie. Use names for tie-breaker.

Using an Object-Oriented Approach

To apply object-oriented principles in this situation, we want to bundle together related data, and abstract away details. That means we want to create an object to associate the name and titles of a given person, and implement functionality to allow each person to be compared with other people.

This will allow us to create two people and compare them with greater than, less than, or equal to operators. More importantly, this will also allow us to perform sorting.

Our Java program Classy is a simple driver that loads the names and titles of people from standard input.

The Person class stores associated name and title data for each person. This class implements the Comparable interface, which requires it to implement a compareTo() method.

class Person implements Comparable<Person> {

    ...

    public int compareTo(Person p2) { 

The Person class constructor just tokenizes one line of input, populating the titles list and the person's name. Here is the declaration of those private fields:

class Person implements Comparable<Person> {
    private String name;
    private ArrayList<String> titles;

    ...

The implementation of the compareTo method utilized Stack objects to examine the sequence of titles in reverse.

Pop the stacks until one of them is empty. Then, keep popping until both are empty, using "middle" in place of the empty stack.

    /** Compare a person to another person. */
    public int compareTo(Person p2) { 

        Stack<String> st1 = new Stack<String>();
        Stack<String> st2 = new Stack<String>();

        // Add names to stack, left to right
        for(String title : this.getTitles()) {
            st1.push(title);
        }
        for(String title : p2.getTitles()) { 
            st2.push(title);
        }

        // Compare each name, from right-to-left.
        // If stack 1 is not empty, pop next item, otherwise use "middle"
        // If stack 2 is not empty, pop next item, otherwise use "middle"

        int max = Math.max(this.getTitles().size(), p2.getTitles().size());
        for(int i=0; i<max; i++) {

            // Pop names from the stack, right to left.
            String s1, s2;

            if(!st1.isEmpty()) {
                s1 = st1.pop();
            } else {
                s1 = "middle";
            }

            if(!st2.isEmpty()) {
                s2 = st2.pop();
            } else {
                s2 = "middle";
            }

            // Rather than converting strings to numbers,
            // compare the strings directly (lower < middle < upper).
            int res = s2.compareTo(s1);

            // Return the first non-zero value
            if( res != 0 ) {
                return res;
            }
        }

        // If we reach here, there was a tie.
        // Use name as tie breaker.
        return this.getName().compareTo(p2.getName());
    }

Code

Here is the entire Classy code, also available on git.charlesreid1.com:

import java.util.*; 
import java.io.*;
public class Classy { 

    public static void main(String[] args) { 
        Scanner s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));

        // Read the input file: new Person for each line
        int n = Integer.parseInt(s.nextLine());
        ArrayList<Person> people = new ArrayList<Person>();
        while(s.hasNextLine()) {
            String line = s.nextLine();
            String[] deets = line.split(" ");
            Person p = new Person(deets);
            people.add(p);
        }

        Collections.sort(people);
        for(Person p : people) { 
            System.out.println(p);
        }
    }
}

class Person implements Comparable<Person> {
    private String name;
    private ArrayList<String> titles;

    /** Person constructor - pass in a String array with the deets. */
    public Person(String[] deets) { 
        name = deets[0];
        // Remove : from name
        name = name.substring(0,name.length()-1);

        // initialize list of classes 
        titles = new ArrayList<String>();
        for(int i=1; i<deets.length-1; i++) { 
            titles.add(deets[i]);
        }
        // Last word will be "class", so ignore.
    }

    /** Get a person's name. */
    public String getName() { return name; }

    /** Get a person's titles in an ArrayList. */
    public ArrayList<String> getTitles() { return titles; }

    /** Get a string representation of a person. */
    public String toString() { return getName(); }

    /** Compare a person to another person. */
    public int compareTo(Person p2) { 

        Stack<String> st1 = new Stack<String>();
        Stack<String> st2 = new Stack<String>();

        // Add names to stack, left to right
        for(String title : this.getTitles()) {
            st1.push(title);
        }
        for(String title : p2.getTitles()) { 
            st2.push(title);
        }

        // Compare each name, from right-to-left.
        // If stack 1 is not empty, pop next item, otherwise use "middle"
        // If stack 2 is not empty, pop next item, otherwise use "middle"

        int max = Math.max(this.getTitles().size(), p2.getTitles().size());
        for(int i=0; i<max; i++) {

            // Pop names from the stack, right to left.
            String s1, s2;

            if(!st1.isEmpty()) {
                s1 = st1.pop();
            } else {
                s1 = "middle";
            }

            if(!st2.isEmpty()) {
                s2 = st2.pop();
            } else {
                s2 = "middle";
            }

            // Rather than converting strings to numbers,
            // compare the strings directly (lower < middle < upper).
            int res = s2.compareTo(s1);

            // Return the first non-zero value
            if( res != 0 ) {
                return res;
            }
        }

        // If we reach here, there was a tie.
        // Use name as tie breaker.
        return this.getName().compareTo(p2.getName());
    }
}

References

1. "ACM Pacific Region Programming Competition." Association of Computing Machinery. 19 June 2017. <http://acmicpc-pacnw.org/>

2. "finalproject-143 (git repository)." Charles Reid. Modified 16 June 2017. Accessed 23 June 2017. <https://git.charlesreid1.com/cs/finalproject-143/src/master/classy/Classy.java>