Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Mattias Waldau <mattias.waldau@a...>
Subject: RE: sorting of list of vectors (array with one dimension)
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

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;
              - : 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;

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