# CSE 143 Final Project: Hilbert Sort: 3. The Code

Posted in Computer Science

This is the third in a series of three posts detailing the Hilbert Sort problem, its solution, and its implementation. This post deals with the code to solve the Hilbert Sort problem.

# Hilbert Sort: Pseudocode

From our prior post, here is the psudocode for our 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
if in northwest:
create new point using X -> 2X, Y -> 2Y - S
if in northeast:
create new point using X -> 2X - S, Y -> 2Y - S
if in southeast:
create new point using X -> S - 2Y, Y -> 2S - 2X

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


Because we are manually sorting, and we want order to be preserved, we should be using a queue to organize points as we sort them. That way, we add them in sorted order, and we are then able to remove them in sorted order.

# Hilbert Sort: Code

We begin by covering a utility class used by the Hilbert Sort method to store $$(X,Y)$$ points. This is a simple example of a composition design pattern. Next, we cover the bulk of the problem solution: the recursive sort method that partiions points into quadrants. Finally, we cover the main method, which demonstrates reading data from an input file and passing it to the sort method.

## Hilbert Sort: Utility Classes

To organize $$(X,Y)$$ point data, we use a simple class using composition. This is defined next to the HilbertSort class.

/**
* An (x,y) Point class.
*/
class Point {
int x, y; // (x,y) point.
String name; // Each (x,y) point has a name in the file. Used for output.
/** Constructor. */
public Point(int x, int y, String name) {
this.x = x; this.y = y; this.name = name;
}
/** String representation (x,y). */
public String toString() {
return "("+this.x+","+this.y+","+this.name+")";
}
}


## Recursive Sort Function

Following is the recursive sort method, which (like merge sort) consists of a split step, which partitions an $$S \times S$$ square into quadrants and distributes points in the square into their corresponding quadrants, and a merge step, which stitches together each quadrant in the correct order.

    /** Recursive implementation of a Hilbert sort. */
public static Queue<Point> hilbertSort(Queue<Point> inputP, int S) {
// Recursive method:
// Apply the Hilbert geometrical quadrant division
// to sort points by when they are visited by a Hilbert curve.
//
// Base case:
// There are 1 or fewer points in each quadrant.
// Keep splitting into quadrants until we reach the base case.
if(inputP.size()<1) {
} else if(inputP.size()==1) {
return inputP;
}

// Sort points by dividing into quadrants
for(Point p : inputP) {

// Prepare for the tricky part.
//
// Rotate the quadrant, and points in it,
// so that everything is now translated to fit
// how the template of the Hilbert curve is being drawn.
// (SW->NW->NE-SE)

boolean inSWquadrant = (2*p.x <= S) && (2*p.y <= S);
boolean inNWquadrant = (2*p.x <= S) && (2*p.y >= S);

boolean inNEquadrant = (2*p.x >= S) && (2*p.y >= S);
boolean inSEquadrant = (2*p.x >= S) && (2*p.y <= S);

// Each time we sort (x,y) points into quadrants,
// we also transform each coordinate point
// in such a way that it rescales to an S x S square,
// but does not modify the order of the points.
//
// Note that we can keep everything as integers by
// continuing to look at an S x S square,
// and double the x and y values to shift them over/up.
//
// Two easy cases:
// - shift y down by S/2
// - keep x and y in same order
qNW.add( new Point(2*p.x, 2*p.y-S, p.name) );

// - shift x and y down by S/2
// - keep x and y in same order
qNE.add( new Point(2*p.x - S, 2*p.y - S, p.name) );

// - x and y need to swap places
// - that's it.
qSW.add( new Point(2*p.y, 2*p.x, p.name) );

// - We want to preserve S - x, distance from right side
// - we want to use it as the new y coordinate
qSE.add( new Point(S - 2*p.y, 2*(S - p.x), p.name) );

}

}
// Sort til you reach the base case.
qSW = hilbertSort(qSW, S);
qNW = hilbertSort(qNW, S);
qNE = hilbertSort(qNE, S);
qSE = hilbertSort(qSE, S);

return result;
}


## Main Method

The last part of the code is the portion that loads the points and their labels from a file, and populates a Queue of Point objects from it. This queue of points is then sorted and returned in order.

    /** Main driver. */
public static void main(String[] args) {

int n = stdin.nextInt();
int S = stdin.nextInt();

// n lines of 3 tokens each
for(int i=0; i<n; i++) {
int x0 = stdin.nextInt();
int y0 = stdin.nextInt();
String label = stdin.next();