Re: sorting of list of vectors (array with one dimension)

[John Max Skaller <skaller@ozemail.com.au>]

Mattias Waldau wrote:
> 
> I have a list of vectors, I would like to sort according to the first
> vector, and move the corresponding data in the other vectors.
> 
> Is there a function for this (for example, a sort function, where I add a
> function that is called each time data is swapped) or do I have to write a
> quicksort in ocaml.

Indirection is the solution to everything :-)

Make a vector of indexes, initially 0,1,2,3 ... n-1,
and sort them with a 'compare' routine which looks at your first vector.

When finished, reorganise all the vectors in the new order indicated
by the indices. You can now move the element that should be in slot 0
there,
saving the old contents of slot 0, 
and rippling through the first cycle until the location for the saved
data is freed. The problem is to find the next cycle. The easiest way I
can think
of is to flag which slots have been fixed, and find any one that has
not,
if any, and start the ripple again from there. I don't see, immediately,
how to do this in less than linear time. Anyone?

Example: sorting "helowrd"
                  0123456

leads to "dehlorw"
          6102354

so we have to move: 6->0, 1->1, 0->2, 2->3, 3->4, 5->5, 4->6.
The cyclic decomposition is:

	(60234)(1)(5)



-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net