== Quote from Walter Bright (newshound1@digitalmars.com)'s article
> Bill Baxter wrote:
> > It seems to me that the built-in .sort uses a randomized algorithm that leads to results that differ from run-to-run when there are elements with identical keys.
> No, it doesn't use random sorts. The source code is included, so this should be easy to verify.

I don't know if it helps, but the built-in sort uses a similar algorithm to the sort routine in tango.core.Array.  It picks a "median of 3" value for the pivot.  As Walter said, I don't believe any randomness is involved.


Sean

Sean Kelly wrote:
> == Quote from Walter Bright (newshound1@digitalmars.com)'s article
>> Bill Baxter wrote:
>>> It seems to me that the built-in .sort uses a randomized algorithm
>>> that leads to results that differ from run-to-run when there are
>>> elements with identical keys.
>> No, it doesn't use random sorts. The source code is included, so this
>> should be easy to verify.
> 
> I don't know if it helps, but the built-in sort uses a similar algorithm
> to the sort routine in tango.core.Array.  It picks a "median of 3" value
> for the pivot.  As Walter said, I don't believe any randomness is involved.
> 
> 
> Sean

I think Bill speaks about a stable sort. You can have an unstable sort algorithm without having explicity a random invocation. Note that he's saying "leads to results that differ from run-to-run when there are elements with identical keys".

Ary Borenszweig wrote:
> I think Bill speaks about a stable sort. You can have an unstable sort algorithm without having explicity a random invocation. Note that he's saying "leads to results that differ from run-to-run when there are elements with identical keys".

And I believe that the sort implementation is completely deterministic. If Bill is getting different results from different runs, something else is going on.

On Wed, Jan 7, 2009 at 4:09 AM, Walter Bright <newshound1@digitalmars.com> wrote:
> Ary Borenszweig wrote:
>>
>> I think Bill speaks about a stable sort. You can have an unstable sort algorithm without having explicity a random invocation. Note that he's saying "leads to results that differ from run-to-run when there are elements with identical keys".
>
> And I believe that the sort implementation is completely deterministic. If Bill is getting different results from different runs, something else is going on.
>

Really?  Hmm, I wonder what the reason was, then.  It did go away when
I switched to a different sort routine.
Don't have time to investigate right now, unfortunately.  But thank
you very much for the info that it should be deterministic.

--bb

On Tuesday, 6 January 2009 at 01:18:21 UTC, bearophile 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]


I'm now looking for np.argsort, and found this post.

@bearophile, the doc page above is gone, although the zip file is still there (~10 years old), do you want to create a github repo, and contribute the code to dub (https://code.dlang.org/)?


BTW, does anyone know if there is a np.argsort function in some other d libraries?


Thanks.

On Tuesday, 23 March 2021 at 21:22:25 UTC, mw wrote:
> [snip]
>
> I'm now looking for np.argsort, and found this post.
>
> @bearophile, the doc page above is gone, although the zip file is still there (~10 years old), do you want to create a github repo, and contribute the code to dub (https://code.dlang.org/)?
>
>
> BTW, does anyone know if there is a np.argsort function in some other d libraries?
>
>
> Thanks.

import std.algorithm.sorting: makeIndex;
import std.algorithm.comparison: equal;
import std.range: indexed;

void main() {
    int[] arr0 = [ 2, 3, 1, 5, 0 ];
    int[] arr1 = [ 1, 5, 4, 2, -1 ];

    auto index = new int[arr0.length];
    makeIndex!("a < b")(arr0, index);
    assert(index == [4, 2, 0, 1, 3]);
    auto view = arr1.indexed(index);
    assert(view.equal([-1, 4, 1, 5, 2]));
}