Jump to content
  • Advertisement
Sign in to follow this  
darcmagik

Sorting a Linked List

This topic is 2620 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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:

#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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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???

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!