Мой MergeSort показывает неправильный вывод, что вы думаете не так с моим кодом?

Question

Мой MergeSort показывает неправильный вывод, что вы думаете не так с моим кодом?

    List List:: mergesort(List m)
{
if(m.count() <= 1)
return m;
else
{
List l,r;
node* temp = m.head;
node* ptemp = m.head;
node* first = m.head;
int c = m.count();
for(int i = 1; temp->next!=NULL && i<=(c/2)+1; i++)
{
ptemp = temp;
temp = temp->next;
}

ptemp->next = NULL;

while(first!=NULL)
{
l.insert(first->data);
first = first->next;
}

while(temp!=NULL)
{
r.insert(temp->data);
temp = temp->next;
}

cout<<"\t\t";
l.display();
cout<<"\t\t";r.display();cout<<"\n";

l = mergesort(l);
r = mergesort(r);
}
}

Я пытаюсь показать каждый шаг во время «деления шага алгоритма сортировки слиянием».

Например, я ввел этот список: 5 3 7 14 2

Желаемый результат: —

              5 3 7 14 2

5 3 7                  14 2

5 3      7              14     2

5     3     7           14         2

что я получаю это:

              5 3 7 14 2

5 3 7                  14 2

5 3                    7

5                      3
14                     2

Что я должен делать? Я перепробовал все возможные вещи, но даже не могу подобраться.
Может ли кто-нибудь помочь, пожалуйста?

хорошо, это то, что я понимаю после отладки,
Что происходит внутри функции mergesort ():

mergesort (5 3 7 14 2)

Слияние (5 3 7)

Слияние (5 3)

mergesort (14 2)

Что мне нужно это: —

mergesort(5 3 7 14 2)
mergesort(5 3 7)
mergesort(14 2)
mergesort(5 3)

Я не могу думать ни о чем. Помогите, пожалуйста.

-1

c++mergesort output

Решение

Другие решения

То, как я пытался бы создать дерево, подобное тому, которое вы описываете (хотя не совсем идентично, потому что mergesort() не создает другой уровень для последовательности из одного элемента), чтобы построить дерево промежуточных состояний, а затем использовать Поиск в ширину прогулка по дереву, чтобы на самом деле показать его. Альтернативой фактическому построению дерева как отдельной структуры данных, вы могли бы реализовать mergesort() не использовать рекурсию, а самостоятельно контролировать промежуточные шаги, эффективно используя обход по ширине неявного дерева.

Ниже приведен пример того, что я имею в виду. Вывод неправильно отформатирован, но, по крайней мере, каждая строка содержит ожидаемый контент. Кроме того, выходные данные показывают промежуточные результаты как разделения, так и промежуточных слияний.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std::placeholders;

typedef std::vector<int> range;

std::ostream& print_range(std::ostream& out, range const& v)
{
out << '[';
if (!v.empty()) {
std::copy(v.begin(), v.end() - 1,
std::ostream_iterator<int>(out, ", "));
out << v.back();
}
return out << "] ";
}

std::vector<range>
mergesort(std::vector<range> const& rs)
{
std::cout << "> ";
std::for_each(rs.begin(), rs.end(),
[](range const& r) { print_range(std::cout, r); });
std::cout << "\n";
if (rs.end() != std::find_if(rs.begin(), rs.end(),
[](range const& r) {
return 1 < r.size();
})) {
std::vector<range> sr;
std::for_each(rs.begin(), rs.end(),
[&](range const& r) {
sr.push_back(range(r.begin(),
r.begin() + r.size() / 2));
sr.push_back(range(r.begin() + r.size() / 2,
r.end()));
});
sr = mergesort(sr);
std::vector<range> result;
for (range::size_type i(0); i + 1 < sr.size(); i += 2) {
result.push_back(range());
std::merge(sr[i].begin(), sr[i].end(),
sr[i + 1].begin(), sr[i + 1].end(),
std::back_inserter(result.back()));
}
std::cout << "< ";
std::for_each(result.begin(), result.end(),
[](range const& r) { print_range(std::cout, r); });
std::cout << "\n";
return result;
}
else {
return rs;
}
}

range mergesort(range const& input)
{
return mergesort(std::vector<range>(1, input)).front();
}

int main()
{
try
{
range input{std::istream_iterator<int>(std::cin),
std::istream_iterator<int>()};
mergesort(input);
}
catch (std::exception const& ex)
{
std::cout << "ERROR: " << ex.what() << '\n';
}
}

0

Источник

Accepted Answer

Вы неправильно выкладываете дерево. Вы никогда не отобразите «дерево слияния» таким образом, потому что вы не можете двигаться вверх в консоли. Вместо этого вы должны повернуть дерево на 90 градусов. Как это

List List:: mergesort(List m, int depth)
{
for (int i = 0; i < depth; ++i)
cout << '\t';
display();
cout << '\n';

...
l = mergesort(l, depth + 1);
r = mergesort(r, depth + 1);

}

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

1