Сергей Деревяго

Алгоритм сортировки DerSort

1. Введение

Quicksort был создан в 1959 году. Он старше всех нас. Но ничего лучшего для общего применения так и не появилось (не считая гибридов).

66 лет целенаправленного поиска блистательных умов... А найдется ль сегодня хоть что-нибудь новое? Да, полировка особых случаев.

А если Фундаментально?

Против всякого чаяния, как ни странно, нашлось!

С уважением, Сергей Деревяго.

2. Перестановка инкрементом

А не громко ли сказано? Ну, давайте прикинем: Остановимся и подумаем...

Хорошо, продолжаю.

Допустим, у нас есть некий вектор v={14, 11, 10, 13} и перестановка p={3, 1, 0, 2}, упорядочивающая его элементы:

i0123
v[i]14111013
p[i]3102
v[i] -> v2[p[i]]10111314

Т.е. используя перестановку p, мы можем перенести каждый элемент v[i] в позицию p[i] и получить упорядоченный вектор v2.

А теперь в конец вектора v мы добавим 12 -- что нужно сделать с перестановкой? Позицией 12-ти обязана стать 2, но она уже занята:

i01234
v[i]1411101312
p[i]3102
v[i] -> v2[p[i]]10111314

Не беда:

  1. Увеличим на 1 все элементы, чье значение >=2.
  2. И добавим 2 в ее конец.
Вуаля!

i01234
v[i]1411101312
p[i]41032
v[i] -> v2[p[i]]1011121314

Гениальное просто. Как и функция добавления: 

void append_pos(vector<short>& perm, short pos)
{
    for (int i=0; i<perm.size(); i++) {
        if (perm[i]>=pos) perm[i]++;
    }
    perm.push_back(pos);
}

Упражнение для читателя: а что, если декрементом? А не с нуля??

3. Реализация DerSort

Все выглядит довольно просто:

derslib\inc\ders\dersort.hpp 
template<class T, class C>
short* dersort(const T* first, const T* last, short* firstOut, C cmp)
{
    auto lastOut=firstOut;
    if (last<=first || last-first>SHRT_MAX) return lastOut;

    *lastOut++=0;

    short base=0;
    for (int i=1; i<last-first; i++) {
        int psz=lastOut-firstOut, beg=0, end=psz;

        for (int j=i-1; j>=0; j--) {
            auto pj=firstOut[j]-base;
            if (pj<beg || pj>=end) continue;

            if (cmp(first[i], first[j])) {
                if (pj==0) {
                    *lastOut++=--base;
                    break;
                }

                end=pj;
            }
            else {
                if (pj==psz-1) {
                    *lastOut++=psz+base;
                    break;
                }

                beg=pj+1;
            }

            if (beg==end) {
                append_pos(base, firstOut, lastOut, beg);
                break;
            }
        }
    }

    if (base) for (auto it=firstOut; it<lastOut; it++) *it-=base;

    return lastOut;
}

void append_pos(short& base, short* first, short*& last, short pos)
{
    auto pb=pos+base;

    int sz=last-first;
    if (pos>=sz/2) {
        int cnt=sz-pos;
        for (auto it=last-1; cnt>0; it--) {
            if (*it>=pb) {
                (*it)++;
                cnt--;
            }
        }
    }
    else {
        int cnt=pos;
        for (auto it=last-1; cnt>0; it--) {
            if (*it<pb) {
                (*it)--;
                cnt--;
            }
        }

        base--;
    }

    *last++=pos+base;
}

void to_sequence(const short* first, const short* last, short* firstOut)
{
    for (int i=0, end=last-first; i<end; i++) firstOut[first[i]]=i;
}

А вот ключевые моменты:

  1. dersort() никак не изменяет сам массив! Он создает перестановку.
  2. Перестановка -- это массив позиций. Присвойте v2[i]=v[p[i]] и вы получите отсортированный массив v2.
  3. Интерфейс dersort() реализован в стиле STL: пара [first, last[ задает массив для сортировки, а перестановка будет записана в firstOut.
  4. Во время вызова, аргумент firstOut должен указывать на массив short той же длины: last-first.
  5. dersort() возвращает lastOut -- конец записанной перестановки.
Ну и самое интересное!

Обратите внимание, что сравнение элементов массива с помощью cmp(first[i], first[j]) вызывается, ТОЛЬКО если pj лежит в диапазоне [beg, end]! А сам диапазон стремительно сужается: в среднем в два раза за шаг.

Таким образом, количество сравнений элементов стремится к минимально возможному, а массив сортируется "сам о себя". Т.е. диапазон [beg, end] сам собой формирует чарующее дерево сравнений.

4. Функция to_sequence()

Так, хорошо. А что же to_sequence()?

Я знал, что вы спросите! Для начала посмотрим на тесты и функцию show():

perf8\main.cpp 
void show(fd_file* out)
{
    // ...

    vector<short> p(v.size());
    dersort(v.data(), v.data()+v.size(), p.data(), [](int a, int b) { return a<b; });
    print(out, "p[i]", &p);

    vector<short> s(p.size());
    to_sequence(p.data(), p.data()+p.size(), s.data());
    print(out, "s[i]", &s);

    // ...
}

Она выводит на экран перестановку p:

i0123456
v[i]14161915151217
p[i]1462305

Можем ли мы с ее помощью отсортировать вектор v? Да не вопрос!

Гы, лихо вы это тут! Но у матросов еще вопросы: как напечатать один за одним отсортированные элементы?

Гмм... Первый элемент перестановки -- савсэм адын, а нам нужно начать с нулевого. И потом уже будут 1, 2 и прочие... Всех придется искать перебором??

Вот поэтому нужен to_sequence()! Мы применим его к результату dersort() и получим перестановку s:

i0123456
v[i]14161915151217
p[i]1462305
s[i]5034162
v[s[i]]12141515161719

Все реально прекрасно, как кажется: v[s[i]] нам выводит один за одним элементы!

5. perf8: производительность DerSort

Мы будем сравнивать с прямыми конкурентами: std::sort() (вариант Quicksort) и ins_sort() (классический Insertion sort).

Увы, но это не привычный тест на скорость, т.к.

Так что прямо в лоб не получается, а наличие/отсутствие дополнительного шага всегда вызывает вопросы...

Тем не менее, есть два ключевых параметра, которые можно сравнить:

  1. Перестановки. DerSort их вообще не использует. Ноль!
  2. Сравнения. DerSort-у их нужно поменьше. Порой в сотни раз!!
Мы будем сравнивать количество сравнений:

perf8\main.cpp 
for (int j=0; j<M; j++) {
    vector<int> v;
    for (int i=0; i<N; i++) {
        if (what=="asc") v.push_back(i);
        else if (what=="desc") v.push_back(N-i);
        else v.push_back(rand());
    }

    vector<short> p(v.size());
    auto plast=dersort(v.data(), v.data()+v.size(), p.data(),
        [](int a, int b) { dersCnt++; return a<b; });
    perm_assert(plast-p.data()==int(p.size()));

    vector<int> v2(v);
    sort(v2.begin(), v2.end(),
        [](int a, int b) { stdCnt++; return a<b; });

    for (int i=0; i<int(v.size()); i++) {
        perm_assert(v[i]==v2[p[i]]);
    }

    vector<int> v3(v);
    ins_sort(v3.data(), v3.data()+v3.size(),
        [](int a, int b) { insCnt++; return a<b; });

    perm_assert(v2==v3);
}

Итак, случайные данные. Запускаем main с аргументом rand и любуемся:

NQuicksortInsertion sort
101.291.21
1001.223.98
10001.0922.89

Мы видим, что:

Вдумайтесь! DerSort-у в среднем хватает O(N*log(N)) сравнений. И их даже меньше, чем надо Quicksort!!

Уже отсортированные данные. Запускаем с аргументом asc:

NQuicksortInsertion sort
102.001.00
1006.351.00
100010.631.00

Мы видим, что:

Отсортированные в обратном порядке. Запускаем с аргументом desc:

NQuicksortInsertion sort
101.005.00
1005.3150.00
10008.15500.00

Мы видим, что:

Вдумайтесь! В отличие от Insertion sort, DerSort идеален в обоих случаях!!

6. Заключение

А теперь подведем итоги: Гмм, квадратичный алгоритм? Кому вообще оно сдалось!

А дело в том, что массив short средних размеров гарантированно помещается в кэш первого уровня. И это ОГРОМНОЕ преимущество!

Вот почему Quicksort не задавил все квадратичные, а примитивный Insertion sort все еще рулит в районе тщедушных массивов. Непромедлительно сравним:

В общем, DerSort нужно использовать: А не использовать? Ну и шпаргалка для двоечников:
Copyright © С. Деревяго, 2025

Никакая часть данного материала не может быть использована в коммерческих целях без письменного разрешения автора.