Simple Sort

Intro

STATUS: Working. More sorts need to be implemented.

Sort in 2D and 3D so that all elements in the array can be visited only once from the start of the array to the finish.

In 2D the curve snakes from left to right, up to down. In 3D it does the same with slices, just reversing the transversal direction of the previous slice. The complexity is O(nlogn).

More strange orderings may be possible. For example while I divided the array into rectangular grids and ordered on the axes, if you come up with other axes or partitions you could possibly order on them instead.

Source

Files

Doxygen

TODO

• Theory that maps the sort to an integer matrix.
  Then the question becomes how to transverse this matrix as all points are treated equally.
• Snake with integer indexes in 3D.
• Onion 3D
  on one cube face spiral inside out, then wrap around like string around the 4 faces moving towards the other end of the cube. Finally spiral in on the last face. Repeat for the next onion layer.
  
  Find/construct an algorithm that given a surface of points where each point has 4 neighbors, a path can be constructed that visits each point once.
• Implement Hilbert curve in 2D.
  Do not worry about the curves complexity.
• Implement Hilbert curve in 3D.
• 2D - radial and 3D spherical sorts.
  Calculate the median. 2D sort on distance from the center and angle. 3D sort on distance from the center, latitude and longitude about a reference.
• Discuss stability and the need for different sorts.