Ok I'm working through some examples and exercises in my C++ book and I'm learning all about the ins and outs of linked lists, stacks, binary trees and such and I'm working on an exercise that requires me to sort a linked list. I've been doing research on sorting linked lists and have come to the conclusion that a merge sort is the best routine but the problem is that I'm having a hard time finding a good example of the algorithm to do so. I found one example of a merge sort on a linked list and tried to implement it into my class template linked list class but the list itself is not updating not to mention I'm having a hard time following their algorithm. So I guess what I'm asking is does anybody know of a good source for a linked list merge sort algorithm preferably something that's C++ oriented (if that makes sense).
Thanks in advance.
Sorting a Linked List
If you show us your code, we might be able to see the problems you're having. Link us to the example you're following too.
Try to understand how and why the algorithm works. wikipedia has some good information http://en.wikipedia.org/wiki/Merge_sort (skip the more complicated parts at the end). The algorithm is the same independent of language so if you know your language good enough it shouldn't be too hard to translate pseudo code into C++. Focus on the meaning of the pseudo code statements and not on the syntax.
Author
Ok so first of all here is the example I'm using online [url="http://www.geeksforgeeks.org/archives/7740"]http://www.geeksforgeeks.org/archives/7740[/url] and I'm also looking at http://en.wikipedia.org/wiki/Merge_sort trying to figure it out. Ok here is the code to my linked list system including the merge sort routines.
Here is the node class:
Here is the list class that contains a set of nodes
Now I'm starting to think that I'm looking at this all the wrong way I think that I need to move my merge sort routines outside of the class and have them used on a list? Or I don't know I'm trying to make it so that you can have a list that has its own merge sort routine that updates the list itself. I know I'm close to figuring this out but just need a little help here.
Thanks again.
Here is the node class:
#ifndef LISTNODE_H
#define LISTNODE_H
template<typename NODETYPE> class List;
template<typename NODETYPE>
class ListNode
{
friend class List<NODETYPE>; // make list a friend
public:
ListNode(const NODETYPE &); // constructor
NODETYPE getData() const; // return data in node
private:
NODETYPE data; // data
ListNode<NODETYPE> *nextPtr; // next node in list
};
// constructor
template<typename NODETYPE>
ListNode<NODETYPE>::ListNode( const NODETYPE &info )
: data(info), nextPtr(0)
{
// empty body
}
// return copy of data in node
template<typename NODETYPE>
NODETYPE ListNode<NODETYPE>::getData() const
{
return data;
}
#endif
Here is the list class that contains a set of nodes
#ifndef LIST_H
#define LIST_H
#include <iostream>
#include "listnode.h"
using namespace std;
template<typename NODETYPE>
class List
{
public:
List(); // constructor
~List(); // destructor
void insertAtFront( const NODETYPE & );
void insertAtBack( const NODETYPE & );
bool removeFromFront( NODETYPE & );
bool removeFromBack( NODETYPE & );
bool isEmpty() const;
void print() const;
void mergeSort(ListNode<NODETYPE> **headPtr);
void listSplit(ListNode<NODETYPE>*, ListNode<NODETYPE>**, ListNode<NODETYPE>**);
ListNode<NODETYPE> *sortedMerge(ListNode<NODETYPE>*, ListNode<NODETYPE>*);
ListNode<NODETYPE> *getHead();
private:
ListNode<NODETYPE> *firstPtr; // pointer to first node
ListNode<NODETYPE> *lastPtr; // pointer to last node
// utility function to allocate new node
ListNode<NODETYPE> *getNewNode( const NODETYPE & );
// count of nodes in list(used for sort routine)
int count;
};
// default constructor
template<typename NODETYPE>
List<NODETYPE>::List()
: firstPtr(0), lastPtr(0)
{
// empty body
}
// destructor
template<typename NODETYPE>
List<NODETYPE>::~List()
{
if (!isEmpty() ) // list is not empty
{
cout << "Destroying nodes...\n";
ListNode<NODETYPE> *currentPtr = firstPtr;
ListNode<NODETYPE> *tempPtr;
while (currentPtr != 0) // delete remaining nodes
{
tempPtr = currentPtr;
cout << tempPtr->data << '\n';
currentPtr = currentPtr->nextPtr;
delete tempPtr;
} // end while
} // end if
count = 0;
cout << "All nodes destroyed\n\n";
}
template<typename NODETYPE>
ListNode<NODETYPE> *List<NODETYPE>::getHead()
{
return firstPtr;
}
// insert node at front of list
template<typename NODETYPE>
void List<NODETYPE>::insertAtFront(const NODETYPE &value)
{
ListNode<NODETYPE> *newPtr = getNewNode( value ); // new node
if ( isEmpty() ) // list is empty
firstPtr = lastPtr = newPtr; // new list has only one node
else // list is not empty
{
newPtr->nextPtr = firstPtr; // point new node to previous 1st node
firstPtr = newPtr; // aim firstPtr at new node
}
count++;
}
// insert node at back of list
template<typename NODETYPE>
void List<NODETYPE>::insertAtBack(const NODETYPE &value)
{
ListNode<NODETYPE> *newPtr = getNewNode( value ); // new node
if ( isEmpty() ) // list is empty
firstPtr = lastPtr = newPtr; // new list has only one node
else
{
lastPtr->nextPtr = newPtr; // update previous last node
lastPtr = newPtr; // new last node
} // end else
count++;
}
// delete node from front of list
template<typename NODETYPE>
bool List<NODETYPE>::removeFromFront(NODETYPE &value)
{
if ( isEmpty() )// list is empty
return false;
else
{
ListNode<NODETYPE> *tempPtr = firstPtr; // hold tempPtr to delete
if ( firstPtr == lastPtr )
firstPtr = lastPtr = 0; // no nodes remain after removal
else
firstPtr = firstPtr->nextPtr; // point to previous 2nd node
value = tempPtr->data; // return data being removed
delete tempPtr; // reclaim previous front node
count--;
return true;
}
}
// delete node from back of list
template<typename NODETYPE>
bool List<NODETYPE>::removeFromBack(NODETYPE &value)
{
if ( isEmpty() ) // list is empty
return false;
else
{
ListNode<NODETYPE> *tempPtr = lastPtr; // hold tempPtr to delete
if ( firstPtr == lastPtr ) // list has one element
firstPtr = lastPtr = 0; // no nodes remain after removal
else
{
ListNode<NODETYPE> *currentPtr = firstPtr;
// locate second to last element
while( currentPtr->nextPtr != lastPtr )
currentPtr = currentPtr->nextPtr; // move to next node
lastPtr = currentPtr; // remove last node
currentPtr->nextPtr = 0; // this is now the last node
}
value = tempPtr->data; // return value from old last node
delete tempPtr; // reclaim former last node
count--;
return true;
}
}
// sort the list of values
template<typename NODETYPE>
void List<NODETYPE>::mergeSort(ListNode<NODETYPE> **headPtr)
{
ListNode<NODETYPE> *head = *headPtr;
ListNode<NODETYPE> *listA;
ListNode<NODETYPE> *listB;
// if list is empty or only has 1 entry just return
if ((head == NULL) || (head->nextPtr == NULL))
return;
listSplit(head, &listA, &listB);
// recursive sort of lists
mergeSort(&listA);
mergeSort(&listB);
// re point the head back to beginning of merged list
*headPtr = sortedMerge(listA, listB);
}
template<typename NODETYPE>
void List<NODETYPE>::listSplit(ListNode<NODETYPE> *head, ListNode<NODETYPE> **listA, ListNode<NODETYPE> **listB)
{
ListNode<NODETYPE> *fast;
ListNode<NODETYPE> *slow;
if (head == NULL || head->nextPtr == NULL)
{
*listA = head;
listB = NULL;
}
else
{
slow = head;
fast = head->nextPtr;
// move fast 2 nodes ahead and slow 1 node ahead
while(fast != NULL)
{
fast = fast->nextPtr;
if (fast != NULL)
{
slow = slow->nextPtr;
fast = fast->nextPtr;
}
}
*listA = head;
*listB = slow->nextPtr;
slow->nextPtr = NULL;
}
}
template<typename NODETYPE>
ListNode<NODETYPE> *List<NODETYPE>::sortedMerge(ListNode<NODETYPE> *listA, ListNode<NODETYPE> *listB)
{
ListNode<NODETYPE> *result = NULL;
if (listA == NULL)
return listB;
else if (listB == NULL)
return listA;
if (listA->data <= listB->data)
{
result = listA;
result->nextPtr = sortedMerge(listA->nextPtr, listB);
}
else
{
result = listB;
result->nextPtr = sortedMerge(listA, listB->nextPtr);
}
return result;
}
// is list empty?
template<typename NODETYPE>
bool List<NODETYPE>::isEmpty() const
{
return firstPtr == 0;
}
// return pointer to newly allocated node
template<typename NODETYPE>
ListNode<NODETYPE> *List<NODETYPE>::getNewNode(const NODETYPE &value)
{
return new ListNode<NODETYPE>(value);
}
// display contents of list
template<typename NODETYPE>
void List<NODETYPE>::print() const
{
if ( isEmpty() ) // list is empty
{
cout << "The list is empty\n\n";
return;
}
ListNode<NODETYPE> *currentPtr = firstPtr;
cout << "The list is: ";
while( currentPtr != 0 ) // get element data
{
cout << currentPtr->data << ' ';
currentPtr = currentPtr->nextPtr;
}
cout << "\n\n";
}
#endif
Now I'm starting to think that I'm looking at this all the wrong way I think that I need to move my merge sort routines outside of the class and have them used on a list? Or I don't know I'm trying to make it so that you can have a list that has its own merge sort routine that updates the list itself. I know I'm close to figuring this out but just need a little help here.
Thanks again.
It makes very little difference whether you use a member function or an external function whose first argument is a pointer to a list: They are essentially the same thing. I haven't read your code, but if you understand the algorithm, writing the code shouldn't be too hard. Little diagrams with boxes and arrows help a lot when trying to get all the pointers right.
It looks like the sequence you get from mergeSort is correctly sorted. I think the problem is that you never update the firstPtr and lastPtr.
Author
Ok feel like an idiot lol the problem wasn't the sort routine it was the main program. I was passing a NULL pointer for the initial head pointer so the sort routine was kicking it back immediately without sorting it.
Thanks everybody for the help.
Thanks everybody for the help.
Author
Here is one more quick question related to merge sort that maybe somebody with more experience with it can explain to me. I noticed that when the list contains duplicate values that it has problems. I get results where it doesn't return all values and other times where some duplicates are missing and others are not. Any ideas as to why this is???
It sounds like a bug to me. Try to come up with the smallest example you can where the algorithm fails, and then use a debugger to figure out what the program is doing exactly. Figure out why the code is doing something wrong and fix it.
It looks right to me.
Do you update lastPtr after calling mergeSort?
I would remove the extra test at the top of listSplit. You already guaranteed that the head and next are not NULL just prior to calling it.
I would also write sortedMerge Iteratively rather than recursively. This can be an interesting learning exercise, and by the looks of what you're written already you could probably manage it.
[size="1"]Psst, see my website...
Do you update lastPtr after calling mergeSort?
I would remove the extra test at the top of listSplit. You already guaranteed that the head and next are not NULL just prior to calling it.
I would also write sortedMerge Iteratively rather than recursively. This can be an interesting learning exercise, and by the looks of what you're written already you could probably manage it.
[size="1"]Psst, see my website...
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
