Сортировка контейнеров

[kgksoft]

Цитата:

Сообщение от mazzy

1.
использовать во вложенной функции less переменную _cIndexKey, глобальную по отношению к функции less - безусловный моветон.

это вложенная функция, так что считаю такой подход приемлемым

Цитата:

Сообщение от mazzy

2.
мне кажется, что будут проблемы с пустыми контейнерами (поскольку _cIndexKey и _qsstart инициализируются единицей)

проблем не было, но это только из-за особенностей поведения интерпретатора.
Сделал дополнительную проверку на пустой контейнер

Цитата:

Сообщение от mazzy

3.
вместо вычисления conlen в цикле по неизменному контейнеру, лучше один раз вычислить и хранить в переменной. поскольку conlen каждый раз просматривает контейнер и вычисляет.

Исправил

Цитата:

Сообщение от mazzy

4.
и мне кажется... что будут серьезные проблемы, если контейнер будет содержать одинаковые элементы.

например, как мне кажется (аксапты нет под рукой чтобы проверить), будет неправильно отсротирован такой контейнер

[ [1, 1], [10,10], [1,1], [5,5], [1,1] ]

Нормально отсортировало.

Попутно доделал возможность указывать порядок сортировки для каждого элемента. Исправленная версия:

static container quickSort(
    container   _qsc,
    container   _cIndexKey  = [[1, SortOrder::Ascending]],
    int         _qsstart    = 1,
    int         _qsend      = conlen(_qsc)
    )
{
    int         qsi = _qsstart;
    int         qsj = _qsend;
    container   qsx;
    container   qsKey;

    boolean less(container _c1, container _c2)
    {
        int qsk;
        int idx;
        SortOrder so;
        int len = conlen(_cIndexKey);
        ;

        for (qsk=1; qsk<=len; qsk++)
        {
            [idx, so] = conpeek(_cIndexKey, qsk);
            if (conpeek(_c1, idx) < conpeek(_c2, idx)) return (so==SortOrder::Ascending)?true:false;
            if (conpeek(_c1, idx) > conpeek(_c2, idx)) return (so==SortOrder::Ascending)?false:true;
        }
        return false;
    }
    ;

    if (! conlen(_qsc)) return _qsc;
    qsx = conpeek(_qsc, (_qsstart +_qsend)/2);

    do
    {
        qsKey = conpeek(_qsc, qsi);
        while (less(qsKey, qsx))
        {
            qsi++;
            if (qsi <= conlen(_qsc))
            {
                qsKey = conpeek(_qsc, qsi);
            }
            else
            {
                break;
            }
        }

        qsKey = conpeek(_qsc, qsj);
        while (less(qsx, qsKey))
        {
            qsj = qsj - 1;
            if (qsi > 0)
            {
                qsKey = conpeek(_qsc, qsj);
            }
            else
            {
                break;
            }
        }

        if (qsi <= qsj)
        {
            qsKey = conpeek(_qsc, qsi);
            _qsc = conpoke(_qsc, qsi, conpeek(_qsc, qsj));
            _qsc = conpoke(_qsc, qsj, qsKey);
            qsi++;
            qsj = qsj - 1;
        }
    } while (qsi <= qsj);

    if (_qsstart < qsj)
    {
        _qsc = Global::quickSort(_qsc, _cIndexKey, _qsstart, qsj);
    }
    if (qsi < _qsend)
    {
        _qsc = Global::quickSort(_qsc, _cIndexKey, qsi, _qsend);
    }

    return _qsc;
}

Тестирование:

    container c = [ [1, 2], [10,10], [1,5], [5,5], [1,10] ];
    ;
    
    c = global::quickSort(c, [[1, SortOrder::Descending],[2, SortOrder::Ascending]]);
    // [ [10,10], [5,5], [1, 2], [1,5], [1,10]  ]