[CST-2] Kolmogorov complexity - cost of sorting

[James Sutherland]

On Fri, 31 May 2002, Tom Puverle wrote:

> > For numbers and strings, no. For some other data type, perhaps, but I
> > can't think of any offhand... Tom?
>
> Almost any user defined data type will need to be sorted by comparison by
> pair.
> E.g. an example in C/C++ (I mean it's not quite C but not quite C++ either
> :) )
>
> 	struct Point3D
> 	{
> 		int x,y;
> 	};
>
> 	...
>
> 	Point3D Vertices[1000 * 1000];	//create an interesting image
> 							//show to Neil Dodgson
>
> 	...
> 	//now sort the points, on these criteria:
> 	//increasing x BUT decreasing y
> 	//this is just a different total order
> 	//on the 2-tuples
>
> 	bool Point1BeforePoint2( Point3D * p1, Point3D * p2 )
> 	{
> 		return (p1->x < p2->x) ||	//x coordinate is greater
> 			(p1->x == p2->x && p1->y > p2->y );	//if the x coordinates
> 							//are the same, compare the y's
>
> 	}
>
> I believe James' method couldn't cope with this ( and in fact with a
> countably infinite set of others)

Trivial to remedy... as I said elsewhere, my approach DOES work on
n-dimensional coordinates. Easiest way: walk the list encoding into
integers by left-shifting x by the width of an int, and ORing in (ymax-y).
Sort, convert back. Three operations taking O(n) time.


James.