Reverse mergeSort for doubly linked list

-1


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

c++
codeblocks
mergesort
asked on Stack Overflow Jun 20, 2018 by Jan Krüger

1 Answer

0

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
}
answered on Stack Overflow Jun 20, 2018 by Victor Istomin • edited Jun 20, 2018 by Victor Istomin

User contributions licensed under CC BY-SA 3.0