algorithm - リストランキングアルゴリズム

Question

次のように、任意の順序にすることができる数値のリストを指定します。

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

彼らのランクを表すリストを作成したいと思います。この場合は

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

数値は、実際にはクラスの順序付けられたリストのメンバーです。リストの順序は変わらないことに注意してください。ランクに従ってカウントされるだけです。

(これらの数値は z オーダーを表しますが、他の用途がある可能性があります)

Answer 1

これは私の解決策であり、まだテストされていません:

// 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];

ご覧のとおり、O(n^2) です.... :(