[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20001130 (07:57) 
From:  John Max Skaller <skaller@o...> 
Subject:  Re: sorting of list of vectors (array with one dimension) 
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 ... n1, 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: 61296600850 checkout Vyper http://Vyper.sourceforge.net download Interscript http://Interscript.sourceforge.net