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 XAA11369 for caml-red; Sun, 3 Dec 2000 23:22:42 +0100 (MET)
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA11969 for <caml-list@pauillac.inria.fr>; Fri, 1 Dec 2000 19:45:14 +0100 (MET)
Received: from tor.abc.se (ns.abc.se [195.17.72.11])
	by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id eB1IjDj03475
	for <caml-list@inria.fr>; Fri, 1 Dec 2000 19:45:13 +0100 (MET)
Received: from gateway (dialup-90 [195.17.73.90])
	by tor.abc.se (8.9.3+Sun/8.9.3) with SMTP id TAA22801;
	Fri, 1 Dec 2000 19:45:01 +0100 (MET)
From: "Mattias Waldau" <mattias.waldau@abc.se>
To: "John Max Skaller" <skaller@ozemail.com.au>,
        "Sven LUTHER" <luther@dpt-info.u-strasbg.fr>, <caml-list@inria.fr>
Subject: RE: sorting of list of vectors (array with one dimension)
Date: Fri, 1 Dec 2000 19:44:57 +0100
Message-ID: <HDEEKOMJILGEIHIMAPCDEEEMDLAA.mattias.waldau@abc.se>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: 7bit
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2911.0)
In-Reply-To: <3A26462C.F8AEFA3F@ozemail.com.au>
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Importance: Normal
Sender: weis@pauillac.inria.fr

Nice suggestions changing the data structure, but I can't change it.

Instead, I implemented the indirection trick by Max Skaller. However instead
of finding how to reorder the data, I just use a temporary data structure
instead.

The algoritm is first to find how to reorder (sort_columns_step_1), and then
l the reordering on each array (sort_columns_step_2).

In this example I like to sort the arrays t1,t2 and t3 according to t1

let t1 = [|2;1;4;3|] in
let t2 = [|true;false;false;true|] in
let t3 = [|"mattias";"magnus";"george";"hugo"|] in
let reorder = sort_columns_step_1 t1 in
   sort_columns_step_2 ~reorder t1;
   sort_columns_step_2 ~reorder t2;
   sort_columns_step_2 ~reorder t3;
   (t1,t2,t3);;
              - : int array * bool array * string array =
[|1; 2; 3; 4|], [|false; true; true; false|],
[|"magnus"; "mattias"; "hugo"; "george"|]

and the code is

let sort_columns_step_1 (a:'a array) : int array =
  let a_i = Array.init (Array.length a) (fun ii -> ii) in
  let compare_a = (fun e1 e2 -> compare a.(e1) a.(e2)) in
  Array.sort compare_a a_i;
  a_i

let sort_columns_step_2 ~(reorder:int array) (a:'a array) =
  let a_temp = Array.init (Array.length a) (fun ii -> a.(reorder.(ii))) in
  Array.iteri (fun ii el -> a.(ii) <- el) a_temp

----
Mattias Waldau, CTO
Tacton AB, Saltmatargatan 7, 11359 Stockholm
Mobile +46 70 549 11 12
http://www.tacton.com mailto:mattias.waldau@tacton.com