Есть несколько способов сделать сортировку слиянием, но мне особенно нужно, чтобы она работала как естественная сортировка слиянием.Что происходит в этом алгоритме, так это то, что меньшие списки чисел создаются в файле следующим образом:
Исходный список: 35 27 24 28 31 37 1 4 7 6 8 9
Меньшие разделы списка:[35], [27], [24, 28], [31, 37], [1, 4, 7], [6, 8, 9]
Как вы заметили, каждый раз, когда приходит несортированный списокчерез число, которое меньше его текущей стоимости, создается новая единица.Как только список заканчивается, этот список разбивается на два других списка, например, альтернативным образом:
Первый список: [35], [24, 28], [1, 4, 7]
Второй список: [27], [31, 37], [6, 8, 9]
Последний шаг включает в себя снова объединение двух списков, и значения сравниваются между единицами в первом спискеэлемент и второй элемент списка, как он проходит.Например, первая единица в первом списке сравнивается с первой единицей в списке два и сохраняет номера в порядке.Любые оставшиеся единицы будут добавлены в конце (не показано).
Объединение двух списков: [27, 35], [24, 28, 31, 37], [1, 4, 6, 7, 8, 9]
Этот процесс будет повторяться до тех пор, пока список не будет отсортирован в одном блоке.
У меня все настроено в этом алгоритме для работы, за исключением объединения двух списков, и его крайне сложно отладитьили найдите проблему.Он проходит примерно половину, прежде чем переходит в ошибку сегментации.В любом случае, я не могу использовать STL слияния в этой программе, и все это в связанном списке.
Примечание: конструкторы и другие необходимые функции уже существуют.Я специально пропустил другие функции, чтобы сопереживать определенной функции.
class mergeList
{
public:
//Setters
void setNumber(int item);
void setStart(bool newStatus);
void setEnd(bool newStatus);
void setPrev(mergeList* node);
void setNext(mergeList* node);
//Getters
int getNumber();
bool getStart();
bool getEnd();
mergeList* getPrev();
mergeList* getNext();
private:
int number;
bool startSection;
bool endSection;
mergeList* prev;
mergeList* next;
};
class mergeListObject
{
public:
mergeList* firstNode;
mergeList* lastNode;
void mergeLists(mergeListObject &firstList,
mergeListObject &secondList);
//Other functions in program are in here.
};
void mergeListObject::mergeLists(mergeListObject &firstList,
mergeListObject &secondList)
{
mergeList* combTraverse = firstNode;
mergeList* firstTraverse = firstList.firstNode;
mergeList* secondTraverse = secondList.firstNode;
bool listDone = false;
//This will clear the combination list for insertion
while (combTraverse != NULL)
{
combTraverse->setNumber(-1);
combTraverse->setStart(false);
combTraverse->setEnd(false);
combTraverse = combTraverse->getNext();
}
combTraverse = firstNode;
combTraverse->setStart(true);
while (listDone == false)
{
//This will go until the first list is traversed.
do
{
bool exception = false;
int j = firstTraverse->getNumber();
int k;
//If the second list is still active, this will
//grab its current value for comparison.
if (secondTraverse != NULL)
k = secondTraverse->getNumber();
//Second list is done, will automatically grab
//first list's value and traverse through to the end.
if (secondTraverse == NULL)
combTraverse->setNumber(firstTraverse->getNumber());
else
{
//Both values from both lists are compared.
if (j <= k)
combTraverse->setNumber(firstTraverse->getNumber());
else
{
exception = true;
combTraverse->setNumber(secondTraverse->getNumber());
}
}
//If the first value unit was used, move the first list iterator up.
//Otherwise, the second list's iterator moves up.
if (exception == false)
firstTraverse = firstTraverse->getNext();
else
secondTraverse = secondTraverse->getNext();
exception = false;
}
while (firstTraverse->getEnd() == false);
//If the second list isn't done, this will finish it.
do
{
combTraverse->setNumber(secondTraverse->getNumber());
secondTraverse = secondTraverse->getNext();
combTraverse = combTraverse->getNext();
}
while (secondTraverse->getEnd() == false);
combTraverse->setEnd(true);
//Marks the end of the section and sets the next one,
//considering it isn't the end of the list.
if (combTraverse->getNext() != NULL)
combTraverse->getNext()->setStart(true);
//Both of these should end up at the start of a unit in their own lists.
firstTraverse = firstTraverse->getNext();
secondTraverse = secondTraverse->getNext();
//Are both lists done?
if (firstTraverse == NULL &&
secondTraverse == NULL)
listDone = true;
}
return;
}
int main()
{
mergeListObject one;
mergeListObject two;
mergeListObject combined;
//The two lists are already separated. All
//other functions have already been called.
combined.mergeLists(one, two);
return 0;
}