Randomness in built-in .sort

[Bill Baxter]

On Tue, Jan 6, 2009 at 10:18 AM, bearophile <bearophileHUGS at lycos.com> wrote:
> 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;


Making a permutation array like that is simple and nice, but another
alternative which may be more efficient is to override the "swap(i,j)"
routine used by the sort implementation, and make it swap the i'th and
jth elements of all the arrays that are being sorted.  That can be
done with O(1) extra storage instead of the O(n) required by making to
make a permutation array.  I think it's also hard to avoid O(n) extra
memory for permuting an array.  At least I can't think of how to do it
with out using an extra allocation.

--bb