Efficiently finding the ranks of elements in an array?

Question

How does one find the rank of each element of an array, averaging in the case of ties, efficiently? For example:

float[] rank(T)(T[] input) {
    // Implementation
}

auto foo = rank([3,6,4,2,2]);  // foo == [3, 5, 4, 1.5, 1.5]

The only way I can think of doing it requires allocating 3 arrays:

1. A duplicate of the input array because it has to be sorted and we don't own it.
2. An array to keep track of the order in which the input array was sorted.
3. An array of ranks to return.

Does anyone know how to do this in O(N log N) time and O(1) auxiliary space (meaning the only array we have to allocate is the one we're going to return), or at least get rid of one of the three arrays above?

Answer 1

If you don't own the array I don't think it's possible to do it in O(N log N) and in space O(1).

If the range of elements (how large an element can be) is small, use counting. Count how many are there of each element and then calculate the result array based on the input array using the counting array.

c - is counting result,
C - is cumulative counting
C[i] = c[i] + c[i-1] + c[i-2] + ... + c[0]
result[i] = 1 / c[in[i]] + C[in[i]-1]

Answer 2

Why not just copy and sort the array and go from there? There are plenty of in-place sort algorithms available such as heapsort.

Answer 3

Ok, so you duplicate your input array into foo. Sort foo in-place in O(n log n) time with heapsort. Now, take the first element of your input array and find its rank in foo in O(log n) time using binary search and insert the rank into the ranks array and return it.

Now, you use 2 arrays instead of 3.

Answer 4

You can allocate the array you are going to return (let's call it R), initialize it to 0..n-1 and then "sort" the incoming array (called I) but using the comparison I[R[k]] vs. I[R[j]] instead of the normal R[k] vs. R[j] and then swapping the values in the R array as needed (instead of the values in the I array as usual).

You can implement this indirect sorting using either quicksort or heapsort (or bubblesort but that will mess up your complexity).

You only need to allocate one array - and some stack space for the indices.

Answer 5

Perhaps it would be useful to summarize florin's answer (and the associated comments) with some simple code.

Here's how to do it in Ruby:

arr = [5,1,0,3,2,4]
ranks = (0..arr.length-1).to_a.sort_by{ |x| arr[x] }
# ranks => [2, 1, 4, 3, 5, 0]

And in Python:

arr = [5,1,0,3,2,4]
ranks = range(len(arr))
ranks.sort(key=lambda x:arr[x])
# ranks => [2, 1, 4, 3, 5, 0]

The ranks array tells you that 0 has rank 2, 1 has rank 1, 2 has rank 4, etc. (Of course, those ranks start at zero, not one.)