Эффективный алгоритм для слияния n последовательных отсортированных массивов на месте

Я разрабатываю алгоритм сортировки на месте, который оставляет массив в состоянии, где он в основном представляет собой последовательность отсортированных подпоследовательностей любого размера (большинство из них больше, чем log2(size(array))); то он объединяет указанные подпоследовательности на месте. Как только описанное состояние достигнуто, алгоритм в его текущей форме просто объединяет первые две подпоследовательности, затем объединяет результат со следующей подпоследовательностью и т. Д. Обратите внимание, что во время слияния мы знаем, где начинаются отсортированные подпоследовательности, нам не нужно их снова искать.

Пока он работает нормально, я предполагаю, что эта схема слияния является субоптимальной, и я считаю, что должна быть возможность использовать более умную схему слияния. Лучший алгоритм, о котором я мог думать, - это алгоритм, который ищет наименьшие последовательные отсортированные подпоследовательности и объединяет их, а затем повторяется до тех пор, пока все не будет объединено. Идея состоит в том, что слияние небольших последовательностей сначала дешевле, поэтому мы должны объединить самые большие из них только в конце.

Существует ли более эффективный алгоритм для слияния n последовательных подпоследовательностей?


В соответствии с запросом предположим, что мы хотим отсортировать следующий массив:

10 11 12 13 14 9 8 7 6 5 0 1 2 3 4

Мой алгоритм будет делать то, что совершенно не имеет значения для вопроса, но оставить массив в следующем состоянии:

10 11 12 13 14 0 5 6 7 8 9 1 2 3 4
^              ^           ^

В каретах показано, где достаточно большой отсортированные подпоследовательности в начале массива; в фактическом коде они соответствуют итераторам или индексам в зависимости от используемой абстракции. Следующим шагом будет объединение этих подпоследовательностей для сортировки массива (обратите внимание, что все они больше, чем log2(size(array)), если это имеет значение, но они могут иметь разные размеры). Чтобы объединить разные части этого массива, самый умный ход, по-видимому, должен слить последнюю подпоследовательность с серединой на место, оставив массив в следующем состоянии:

10 11 12 13 14 0 1 2 3 4 5 6 7 8 9
^              ^

... затем два объединяют две оставшиеся подпоследовательности на месте, чтобы массив фактически сортировался. Как я уже сказал, до этапа слияния на месте может быть до log2(size(array)).


Мое текущее решение для шага слияния включает в себя немного косвенности: итераторы, отмеченные каретками, хранятся в списке, затем я создаю кучу минут, где каждый элемент является одним из итераторов списка, а функция сравнения связывает каждый итератор с расстояние между его соседями. Когда две подпоследовательности объединяются, я вывожу значение из кучи и удаляю соответствующие итераторы из списка. Вот в основном то, что делает мой C ++-алгоритм:

template<typename Iterator, typename Compare=std::less<>>
auto sort(Iterator first, Iterator last, Compare compare={})
    -> void
{
    // Code irrelevant to the question here
    // ...
    //

    // Multi-way merge starts here

    std::list<Iterator> separators = { first, /* beginning of ordered subsequences */, last };
    std::vector<typename std::list<Iterator>::iterator> heap;
    for (auto it = std::next(separators.begin()) ; it != std::prev(separators.end()) ; ++it)
    {
        heap.push_back(it);
    }
    auto cmp = [&](auto a, auto b) { return std::distance(*std::prev(a), *std::next(a)) < std::distance(*std::prev(b), *std::next(b)); };
    std::make_heap(heap.begin(), heap.end(), cmp);

    while (not heap.empty())
    {
        std::pop_heap(heap.begin(), heap.end(), cmp);
        typename std::list<Iterator>::iterator it = heap.back();
        std::inplace_merge(*std::prev(it), *it, *std::next(it), compare);
        separators.erase(it);
        heap.pop_back();
    }
}

Я написал алгоритм в C ++, потому что мне легче рассуждать об итераторах, но общий алгоритмический ответ приветствуется.

7 голосов | спросил Morwenn 30 WedEurope/Moscow2015-12-30T21:51:58+03:00Europe/Moscow12bEurope/MoscowWed, 30 Dec 2015 21:51:58 +0300 2015, 21:51:58

1 ответ


1

Если вы повторно объедините две первые последовательности, вы получите время выполнения, которое намного хуже, чем сортировка слияния, поскольку вы сравниваете первые элементы слишком много раз (n log (n) ^ 2 ???), если вы объедините 2 (или более) наименьших (смежных) последовательностей каждый раз, когда вы должны приближаться к эффективности сортировки слияния.

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

---- Редактировать

Первая версия:
Существенный слияние, где разделители являются неявным разделом алгоритма mergesort.

Order separators according to their index in the array

MergeIt(first, last) {
    if (only one or zero separator)
       return first;

    split = separator containing the middle separator (first, last)

    return inplace_merge(MergeIt(first, split), MergeIt(split, end));
}

Это гарантирует, что вы выполняете минимальное количество слияний, но не минимальное количество сравнений, так как более крупные последовательности могут сливаться с текущей минимальной последовательностью.

Версия вторая:
Все еще в основном слияние, где мы теперь учитываем длину последовательностей.

Order separators according to their index in the array

MergeIt(first, last) {
    if (only one or zero separator)
       return first;

    split = separator containing the middle element of array(first, last) // not the middle separator

    return inplace_merge(MergeIt(first, split), MergeIt(split, end));
}

Раскол гарантирует, что меньшие последовательности сливаются сначала, поскольку больший стоп выше в дереве вызовов. Это все еще не гарантирует наименьшее количество сравнений, так как существует вероятность того, что более крупные последовательности сливаются с текущей минимальной длиной, хотя это все же лучше, чем версия 1, поскольку здесь большие значения меньше.

Версия три:
Объедините смежные последовательности, которые охватывают наименьшее количество элементов

Make heap of pairs of adjacent sequences, sort after minimum length of the pairs, for each sequence only add the shortest of its prev and next.
// each sequence will appear max twice except the first and last.

while (heap.size() > 1) {
    min = heap.pop

    remove the possible other occurrence of min.first and min.second

    sequence = inplace_merge(min.first, min.second)

    insert the minimum of pair(prev(sequence), sequence) and pair(sequence, next(sequence)) in heap.
}

Накладные расходы могут сделать это медленнее, чем вторая версия, но сравнения, сделанные inplace_merge, теперь должны быть минимальными.

ответил Surt 31 ThuEurope/Moscow2015-12-31T05:40:38+03:00Europe/Moscow12bEurope/MoscowThu, 31 Dec 2015 05:40:38 +0300 2015, 05:40:38

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132