Понимание и решение K-Way сортировки слиянием

#c# #java #algorithm #data-structures

#c# #java #алгоритм #структуры данных

Вопрос:

Я хочу:

подсчитайте количество сравнений, необходимых для k-Way merge sort, чтобы отсортировать случайную перестановку чисел от 0 до N-1.
подсчитать количество перемещений данных, необходимых для K-Way merge sort для сортировки случайной перестановки чисел от 0 до N-1.

Я понимаю, как правильно работает 2-сторонняя сортировка слиянием, и очень хорошо понимаю код. Моя проблема сейчас в том, что я не знаю, с чего начать. Как мне преобразовать 2-стороннюю сортировку слиянием в K-Way, чтобы я мог решить вышеуказанные проблемы?

Я искал в Интернете, но не могу найти ни одного руководства, которое бы очень хорошо объясняло «k-Way сортировку слиянием».

Мне нужно хорошее объяснение, что делать, чтобы я мог взять его оттуда и сделать это сам.

Как я уже сказал, я понимаю 2-Way, так как мне перейти к K-Way сортировке слиянием? Как мне реализовать K-way?

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

Я прочитал какой-то пост http://bchalk.com/work/view/k_way_merge_sort этот двоичный набор должен использоваться для реализации слияния k-Way. Это так или есть другие способы?

Как мне разделить мой список на K? Есть ли особый способ сделать это?

1. Двоичная куча не требуется для k-way слияния. Все, что вам нужно, это способ быстро найти наименьший в списке из k элементов, удалить этот элемент и поместить другой элемент в список. Двоичная куча часто используется, потому что она проста в реализации и довольно эффективна для небольших списков. Но вы могли бы использовать список пропусков или любую из нескольких других реализаций кучи или какую-либо другую реализацию очереди приоритетов.

Ответ №1:

Когда k > 2 ведущие элементы из каждого из входных потоков обычно хранятся в структуре minheap. Это позволяет легко находить минимальное количество n-значений, извлекать это значение из кучи и вставлять заменяющее значение из соответствующего входного потока.

Куча выполняет O(lg2 k) сравнения для каждой вставки, поэтому общая работа для k-way слияния n элементов составляет n * lg2(k) .

Несмотря на то, что вы спрашивали о C # и Java, вы можете узнать, как это сделать, просмотрев код стандартной библиотеки Python для k-way merge: http://hg.python.org/cpython/file/2.7/Lib/heapq.py#l323

Чтобы ответить на ваш другой вопрос, не существует специального способа разделить ваш список на K групп. Просто возьмите первые N / k элементов в первом массиве, следующие N / k элементов в следующем и т.д. Сортируйте каждый массив, а затем объединяйте их, используя кучи, как упоминалось выше.

Ответ №2:

Вы всегда можете представить k-way merge как серию 2-полосных слияний, то есть выполнить 2-полосное слияние с результатом первого, второго и третьего: Merge(Merge(L1, L2), L3) и так далее. Еще быстрее было бы разделить его дважды : Merge(Merge(L1, L2), Merge(L3, L4)) . Как вы можете видеть, для k-way сортировки вам потребуется какой-то цикл (рекурсия).