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)

Answer 1

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.... :(

Answer 2

I think this is the same question