Eden is a user on queer.cloud. You can follow them or interact with them if you have an account anywhere in the fediverse. If you don't, you can sign up here.
Eden @eden@queer.cloud
Follow

Is there any way of idiomatically finding the sort order of a list, without sorting it?

So if I had
1 4 3 5
It'd return
0 2 1 3

Rather than sorting it into place?
are the communities I usually ping for this sort of thing, but it's kinda language agnostic.

· Web · 4 · 2

@eden i think it's the same amount of work, like calling SELECT on every member of the list

@amphetamine So it seems to be roughly the same amount of work, but there's no Rust sort that gives that you info by default, even though it's used in the function.

@eden hnnnnmmmmm annoying

i could have sworn there was one

if you can use an iterator you can maybe work something out with enumerate()

@eden
In MATLAB, the sort function can also return the indexes/mapping.

@eden Finding sort order is equivalent to sorting the array (if you have sort order getting sorted array is O(N), sorting has usually higher complexity).

Since they are equivalent there is not reason not to sort.

If you need to get sort order just create a list of tuples (1 1), (4, 2), (3, 3) (5, 4) and then sort them using first element, then you'll get sort order.

In numpy you have argsort method which is useful: docs.scipy.org/doc/numpy/refer .

@jacek ooh, I think I can use this. I thought they're not quite equivalent for some types of sort, because you'll move items in blocks rather then repositioning, but I didn't think about adding in an index.

So for my case, I think I can sort tuples in Rust and get the paired index, thanks!

@eden you can just count the numbers that are bigger than the one you want to figure out the position of
@eden duplicates receive the same position in this case

@eden As you mentioned, any sorting algorithm can get you a permutation that sorts the list.

It turns out that it's (asymptotically) optimal, as you can apply the permutation in linear time and constant space, and you can't sort or find a sorting permutation in sublinear time (yes, autocarrot, sublinear is sublimer, but it's not what I meant) because you need to read the whole list.

Interestingly, the classical result about sorting using at least O(n log n) calls to the comparison function (assuming that is the only operation you have on elements) is most easily proved by looking for the sorting permutation:

Let's say you have n distinct items, there is exactly one sorting permutation, out of n! possible permutations.
Since the only way to get information about which permutation it is, is through the comparison function, and that it provides a single bit of information per call, you need at least log2(n!) / (1 bit / call) ~ n log n calls