Randomness in built-in .sort

bearophile bearophileHUGS at lycos.com
Mon Jan 5 17:18:21 PST 2009


Bill Baxter:

>I use this all the time in NumPy in the form of "argsort" which returns a list of indices giving the sort order.  That can then be used as to index other arrays (thereby permuting them to the sorted order).
order = npy.argsort(keys)
sortedA = A[order]
sortedB = B[order]<

My dlibs already contain an efficient sorting routine, much faster than the built in one.

So to my dlibs I have just added sortedIndexes and remapOrder, you can find their docs here:
http://www.fantascienza.net/leonardo/so/dlibs/func.html

The code:
http://www.fantascienza.net/leonardo/so/libs_d.zip

The usage is very simple, sortedIndexes is similar to sorted():

auto a =  [-5, 2, 3, 1, -11].dup;
auto order1 = a.sortedIndexes();
// now order1 == [4U, 0, 3, 1, 2]

auto order2 = a.sortedIndexes((int x){return x < 0 ? -x : x;});
// Now order2 == [3U, 1, 2, 0, 4]

int[2][] c = [[3, 4], [1,2], [1, 1]];
auto order3 = c.sortedIndexes();
// now order3 == [2U, 1, 0]

auto a =  [-5, 2, 3, 1, -11].dup;

a.remapOrder([4, 0, 3, 1, 2]) ==> [-11, -5, 1, 2, 3]
// a isn't changed here
a.remapOrder([3, 1, 2, 0, 4]) ==> [1, 2, 3, -5, -11]

auto b = ["oranges"[], "for", "apples", "is", "right"].dup;
b.remapOrder([3, 1, 2, 0, 4]) ==>
["is"[], "for", "apples", "oranges", "right"].dup);

(Maybe I have to rename remapOrder as remappedOrder).

--------------------------------

While writing the unittest for those functions, I have seen this isn't accepted by DMD:
int[2][] c = [[3, 4], [1, 2], [1, 1]].dup;

While the compiler accepts this, I don't know why:
int[2][] c0 = [[3, 4], [1, 2], [1, 1]];
int[2][] c2 = c0.dup;

Bye,
bearophile



More information about the Digitalmars-d mailing list