List ranking algorithm

Question

Given a list of numbers, which can be in any order, such as

3, -5, -1, 2, 7, 12, -8

I would like to produce a list which represents their rank, which in this case would be

4, 1, 2, 3, 5, 6, 0

The numbers are actually some member of an ordered list of classes. Note that the order of the list does not change, they just get counted according to their rank.

(these numbers represent a z-order, but there could be other uses)

what is important to you ? time ( we could sort and set up a hash) ? — sundeep, Nov 18 '08 at 20:48
I think [this](http://stackoverflow.com/questions/13473/how-does-one-rank-an-array-sort-by-value-with-a-twist) is the same question — AShelly, Nov 18 '08 at 20:47

score 0 · Answer 1 · answered Nov 18 '08 at 20:45

This is my solution, untested as of yet:

// this will be our storage of the new z-order
int *tmpZ = new int[GetCount()];

int currentZ = INT_MIN;
int smallestIdx = -1;
int newZ = 0;
for (int passes = 0; passes < GetCount(); passes++)
{
    int smallestZ = INT_MAX;
    // find the index of the next smallest item
    for (int i = 0; i < GetCount(); i++)
    {
        if (GetAt(i)->m_zOrder > currentZ && GetAt(i) < smallestZ)
        {
            smallestIdx = i;
            smallestZ = GetAt(i)->m_zOrder;
        }
    }
    tmpZ[smallestIdx] = newZ;

    // prepare for the next item
    currentZ = smallestZ;
    newZ++;
    smallestIdx = -1;
}

// push the new z-order into the array
for (int i = 0; i < GetCount(); i++)
    GetAt(i)->m_zOrder = tmpZ[i];

It is O(n^2), as you can see.... :(

List ranking algorithm

1 Answers1