From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id IAA15958 for caml-red; Thu, 30 Nov 2000 08:57:54 +0100 (MET) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id IAA15318 for ; Thu, 30 Nov 2000 08:40:45 +0100 (MET) Received: from localhost.localdomain (jimbo192.zip.com.au [202.7.88.192]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id eAU7eff01858 for ; Thu, 30 Nov 2000 08:40:42 +0100 (MET) Received: from ozemail.com.au (IDENT:root@localhost [127.0.0.1]) by localhost.localdomain (8.9.3/8.8.7) with ESMTP id SAA01648; Thu, 30 Nov 2000 18:37:51 +1100 Message-ID: <3A2603CF.698A368D@ozemail.com.au> Date: Thu, 30 Nov 2000 18:37:51 +1100 From: John Max Skaller X-Mailer: Mozilla 4.7 [en] (X11; I; Linux 2.2.12-20 i686) X-Accept-Language: en MIME-Version: 1.0 To: Mattias Waldau CC: caml-list@inria.fr Subject: Re: sorting of list of vectors (array with one dimension) References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: weis@pauillac.inria.fr 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