Table of Contents

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.

• Pseudocode

• Code

  • Utility Classes
  • Recursive Sort Function
  • Main Method

• References

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
            add to southwest queue
        if in …

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 …

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 …

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 …

Table of Contents

• The Problem
  • Problem Description: Checkers
  • Input File
  • Output
• The Solution
  • Keep It Simple
  • Solution Analysis: Parity
  • Solution Analysis: Graphs and Euler Tours
  • Solution Algorithm
  • Solution Pseudocode
  • Solution Code
• References

The Problem

This is a programming challenge that was assigned to some of my CSE 143 students as a final project for their class.

The origin of this problem was the Association of Computing Machinery (ACM)'s International Collegiate Programming Competition (ICPC), in particular the Pacific Northwest Regional Competition, Division 1 challenges from 2015.

Link to Pacific NW ACM ICPC page.

Problem Description: Checkers

In the Checkers problem …