I have issues with my mergeSort algorithm, the ascending order works, but the descending order doesnt: I made the reverseMerge function for that. It is called, when the sort function is called with ascending = false; Here is the code
#ifndef AUFGABE_MERGESORT_H
#define AUFGABE_MERGESORT_H
#include "List.h"
#include <iostream>
#include "Item.h"
using namespace std;
template <typename T>
class MergeSort
{
public:
void sort(List<T> *list, bool ascending)
{
Item<T> *listHeader = list->head();
list->head()->prev= NULL; //Setze Next des letzen Item auf NULL
Item<T> *current = list->head();
while(current->next != list->head() && current->next != NULL){
current = current->next;
}
current->next = NULL;
listHeader = mergeSort(list->head(), ascending);
current = listHeader;
while(current->next != list->head() && current->next != NULL){
current = current->next;
}
listHeader->prev = current;
current->next = listHeader;
}
Item<T> *merge(Item<T> *first, Item<T> *second) //Funktion um 2 Listen zu mergen
{
// If first linked list is empty
if (!first)
return second;
// If second linked list is empty
if (!second)
return first;
// Pick the smaller value
if (first->e < second->e)
{
first->next = merge(first->next,second);
first->next->prev = first;
first->prev = NULL;
return first;
}
else
{
second->next = merge(first,second->next);
second->next->prev = second;
second->prev = NULL;
return second;
}
}
Item<T> *mergeSort(Item<T> *head, bool ascending) //MergeSort Funktion, rekursiv
{
if (!head || !head->next)
return head;
Item<T> *second = split(head);
// Recur for left and right halves
head = mergeSort(head, ascending);
second = mergeSort(second, ascending);
// Merge the two sorted halves
if(ascending)
return merge(head,second);
else
return reverseMerge(head, second);
}
Item<T> *split(Item<T> *head) //Funktion zum Splitten der linked List in 2 gleich große Listen
{
Item<T> *fast = head,*slow = head;
while (fast->next && fast->next->next)
{
fast = fast->next->next;
slow = slow->next;
}
Item<T> *temp = slow->next;
slow->next = NULL;
return temp;
}
Item<T> *reverseMerge(Item<T> *first, Item<T> *second) //Funktion um 2 Listen zu mergen
{
// If first linked list is empty
if (!first)
return second;
// If second linked list is empty
if (!second)
return first;
// Pick the bigger value
if (first->e > second->e)
{
first->next = reverseMerge(first->next,second);
first->next->prev = first;
first->prev = NULL;
return first;
}
else
{
second->next = reverseMerge(first,second->next);
second->next->prev = second;
second->prev = NULL;
return second;
}
}
};
#endif //AUFGABE_MERGESORT_H
I tried reversing the "<" to a ">". I read that in several other posts here in stackoverflow, but my function gives me a runtime Error. It just crashes, with the following exit code: -1073741819 (0xC0000005). When trying to print it with my print function:
void Application::printArtists()
{
if (database.artistList.isEmpty() == false)
{
Item<Artist> *selectedArtist = database.artistList.first();
while (selectedArtist != database.artistList.head())
{
cout<<selectedArtist->e.getTitle()<<endl;
selectedArtist = selectedArtist->next;
}
}
}
My doubly linked list, has the last element->next pointing to the head of the list, and the head->prev is pointing to the last element of the list, or it should be at least.
Edit: I know, that 005 is a access violation, but I cant find my mistake
Common way of changing sort directions is to use predicate. This way, you'll avoid unnecessary code and bugs duplication:
template <typename T, typename GoesFirstPredicate>
class MergeSort
{
void sort(List<T> *list)
{
...
}
Item<T> *mergeSort(Item<T> *head)
{
...
}
Item<T> *merge(Item<T> *first, Item<T> *second)
{
// If first linked list is empty
if (!first)
return second;
// If second linked list is empty
if (!second)
return first;
GoesFirstPredicate goesFirst;
if (goesFirst(first->e, second->e))
{
// 'first' should be before 'second'
first->next = merge(first->next,second);
first->next->prev = first;
first->prev = NULL;
return first;
}
else
{
// 'second' should be before 'first'
second->next = merge(first,second->next);
second->next->prev = second;
second->prev = NULL;
return second;
}
}
...
};
Then you can use MergeSort<Artist, std::less> ascendingSorter
; and MergeSort<Artist, std::greater> descendingSorter;
.
However, I recommend improve code further by using template functions instead of template classes in order to use automatic template parameters deduction. You can look at std::sort for example.
namecpace mySortsLib
{
template <typename T, typename BinaryPredicate>
void mergeSort(Item<T>* head, BinaryPredicate goesFirst)
{
...
merge(head, second, goesFirst);
...
}
template <typename T, typename BinaryPredicate>
void merge(Item<T> *first, Item<T> *second, BinaryPredicate goesFirst)
{
...
if (goesFirst(first->e, second->e))
...
else
...
}
}
void f()
{
Item<Artist> *selectedArtist = database.artistList.first();
// enjoy automatic template parameter deduction
mySortsLib::mergeSort(selectedArtist, std::less()); // ascending
mySortsLib::mergeSort(selectedArtist, std::greater()); // descending
}
User contributions licensed under CC BY-SA 3.0