Слияние 8 отсортированных списков в C++, какой алгоритм должен, я использую
Все зависит от того, как вы собираетесь использовать Boost. Как сказал Диомидис, если вы собираетесь использовать какие-то нетривиальные средства от Boost, просто продолжайте. Использование библиотек не является преступлением.
Конечно, есть много людей, которые предпочитают не использовать Boost, потому что введение новых зависимостей всегда имеет некоторые недостатки и дополнительные заботы, но в проекте с открытым исходным кодом ... на мой взгляд, это даже нормально использовать если вы просто хотите изучить их или улучшить свои навыки на них.
6 ответов
Простое расширение фазы слияния сортировки слиянием может сделать это за O (n lg m) раз (где n = общее количество элементов и m = количество списков), используя приоритетная очередь (например, куча ). Псевдокод:
Let P = a priority queue of the sorted lists, sorted by the smallest element in each list
Let O = an empty output list
While P is not empty:
Let L = remove the minimum element from P
Remove the first element from L and add it to O
If L is not empty, add L to P
И простая (непроверенная!) Конкретная реализация на C ++:
#include <list>
#include <set>
template<typename T>
struct cmp_list {
bool operator()(const std::list<T> *a, const std::list<T> *b) const {
return a->front() < b->front();
}
};
template<typename T>
void merge_sorted_lists(std::list<T> &output, std::list<std::list<T> > &input)
{
// Use a std::set as our priority queue. This has the same complexity analysis as
// a heap, but has a higher constant factor.
// Implementing a min-heap is left as an exercise for the reader,
// as is a non-mutating version
std::set<std::list<T> *, cmp_list<T> > pq;
for ( typename std::list<std::list<T> >::iterator it = input.begin();
it != input.end(); it++)
{
if (it->empty())
continue;
pq.insert(&*it);
}
while (!pq.empty()) {
std::list<T> *p = *pq.begin();
pq.erase(pq.begin());
output.push_back(p->front());
p->pop_front();
if (!p->empty())
pq.insert(p);
}
}
Вы можете попробовать применить сортировку слиянием по одному к каждому из списков:
http://en.wikipedia.org/wiki/Merge_sort
Это алгоритм для сортировки слиянием. По сути, вы должны пойти со списками 1 и 2 и отсортировать их слиянием. Затем вы возьмете этот новый объединенный список и отсортируете его со списком 3, и так будет продолжаться до тех пор, пока у вас не будет одного полностью отсортированного списка.
РЕДАКТИРОВАТЬ:
На самом деле, поскольку ваши списки уже отсортированы, только последняя часть слияния сортировка будет необходима. Я бы итеративно объединял списки в все большие и большие части, все время сортируя каждый из этих больших списков, пока у вас не будет полный список, что, по сути, и делает сортировка слиянием после того, как она завершена с ее подходом «разделяй и властвуй».
Если производительность не является проблемой, я бы отсортировал списки в последнюю очередь. Код более читабелен, короче и с меньшей вероятностью будет запутан кем-то, кто пересмотрит код в будущем.
This is a standard (although 8-way) merge sort.
Basically you "open" the eight sorted lists then begin processing them, extracting the lowest value each time, something like:
# Open all lists.
open newlist for write
for i = 1 to 8:
open list(i) for read
end for
# Process forever (break inside loop).
while true:
# Indicate that there's no lowest value.
smallidx = -1
# Find lowest value input list.
for i = 1 to 8:
# Ignore lists that are empty.
if not list(i).empty:
# Choose this input list if it's the first or smaller
# than the current smallest.
if smallidx = 1:
smallidx = i
smallval = list(i).peek()
else:
if list(i).peek() < smallval:
smallidx = i
smallval = list(i).peek()
end if
end if
end if
end for
# No values left means stop processing.
if smallidx = -1:
exit while
end if
# Transfer smallest value then continue.
smallval = list(smallidx).get()
newlist.put(smallval)
end while
В основном вы выполняете часть многосторонней сортировки слиянием, за исключением того, что ваш материал уже отсортирован ...
http://lcm.csa.iisc.ernet.in/dsa/node211.html
Просто найдите самый низкий в каждом массиве (почти используется как стеки) и поместите его в вашем выводе, пока все стеки не опустеют ...
Требуется сортировка слиянием . Ваши списки уже разделены, но не до самого нижнего уровня. Вы можете сделать следующее:
unsorted_list = concatenate(list[0], list[1], list[2], ... , list[7]);
sorted_list = merge_sort(unsorted_list);
Эта операция не должна занимать много времени / памяти, потому что конкатенация должна добавить ссылку из последнего узла в списке на первый элемент следующего списка.