Sign in to follow this  
darcmagik

Sorting a Linked List

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
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"][url="http://www.geeksforgeeks.org/archives/7740"]http://www.geeksforgeeks.org/archives/7740[/url][/url] and I'm also looking at [url="http://en.wikipedia.org/wiki/Merge_sort"]http://en.wikipedia.org/wiki/Merge_sort[/url] 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:
[code]
#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
[/code]

Here is the list class that contains a set of nodes
[code]
#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
[/code]

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"][i]Psst, see my website...[/i][/size]

Share this post


Link to post
Share on other sites
Thanks for the advice I updated my code with this:
[code]
// re point the head back to beginning of merged list
firstPtr = sortedMerge(listA, listB);

ListNode<NODETYPE> *currentPtr = firstPtr;

while (currentPtr != 0)
{
currentPtr = currentPtr->nextPtr;
}
lastPtr = currentPtr;
[/code]

at the end of mergesort method. As far as the iterative approach I thought about trying it but wanted to figure out this task first with the duplicates.

So here is the program that I'm using to test these methods:

[code]
#include <iostream>
#include <string>
#include "List.h"
using namespace std;

// function to initialize a list
template<typename T>
void InitList(List<T> &listObject, List<T> &listObject2)
{
cout << "Initializing list 1.\n";

T value;

for (int i = 0; i < 10; i++)
{
cout << "Enter an int value :\n";
cin >> value;

listObject.insertAtBack(value);
}

cout << "Initializing list 2.\n";

for (int j = 0; j < 10; j++)
{
cout << "Enter an int value :\n";
cin >> value;

listObject2.insertAtBack(value);
}
}

template<typename T>
void concatenate(List<T> &listObject1, List<T> &listObject2)
{
T value;
while (!listObject2.isEmpty())
{
listObject2.removeFromFront(value);
listObject1.insertAtBack(value);
}
}

void main()
{
List<int> list1;
List<int> list2;

InitList(list1, list2);

cout << "The 2 lists before they are merged together and sorted.\n";
list1.print();
list2.print();

cout << "Merging 2 lists.\n";
concatenate(list1, list2);
list1.print();

cout << "Sorting the new combined data.\n";
ListNode<int> *headPtr = list1.getHead();
list1.mergeSort(&headPtr);

cout << "New merged oredered list oredered.\n";
list1.print();

system("pause");
}
[/code]

And the data I used to test it with that causes a weird reaction is: 1 1 2 2 3 3 4 4 5 5 5 5 4 4 3 3 2 2 1 1
and the result I get after combining the 2 data sets and then merge sorting them them is: 1 1 2 2 3 3 4 4 5 5 5 5
So I'm confused. I've tried stepping through the routine but haven't figured out why its doing it.

Share this post


Link to post
Share on other sites
I'm guessing you followed a tutorial and typed in your merge sort implementation step by step? If you're trying to learn C++/general programming, I suggest you read the following short description of bubble sort, and try to implement it [b]without looking at reference code[/b]. First do it with an array, and then with a linked list. Great for learning pointers / how handle edge cases / general problem solving skills. (More important imo than implementing a particular data structure. For merge sort, or whatever sort work the algorithm out in your head. Not likely that you'll ever need to implement a vanilla sorting algorithm, ever :D )


[font="sans-serif"][size="2"][quote]The algorithm starts at the beginning of the data set. It compares the first two elements, and if the first is greater than the second, it swaps them. It continues doing this for each pair of adjacent elements to the end of the data set. It then starts again with the first two elements, repeating until no swaps have occurred on the last pass.[/quote][/size][/font]


Also, [font="sans-serif"][size="2"][quote]Merge sort's most common implementation does not sort in place[/quote][/size][/font]

Share this post


Link to post
Share on other sites
[quote name='jameszhao00' timestamp='1318762039' post='4873089']
Also, [font="sans-serif"][size="2"][quote]Merge sort's most common implementation does not sort in place[/quote][/size][/font]
[/quote]
That's because it's usually implemented on arrays. In the case of linked lists, it's easy to write it just moving pointers around, without copying or moving any of the data.

Share this post


Link to post
Share on other sites
Thanks for the advice, I have implemented bubble sort many times in the past on arrays I haven't done so on a linked list maybe I will try that but I didn't bother at first because I know that bubble sort is one of the most inefficient sort routines available to choose. So I was looking for fast and efficient. All and all I feel confident with my abilities with linked lists( at least more than I was before I started this project). Now to take what I've learned and use it in my video game projects as needed.

Share this post


Link to post
Share on other sites
I hope "taking what you've learned" means throwing away your hand rolled class and using std::list<> and std::list::sort() in its place.

In fact, if you're looking for efficiency, std::vector<> should be your go-to container of choice. The theoretical advantages of std::list<> are almost always negated by the allocation overhead and cache trashing that linked lists cause. Until you've profiled, for basic "bag" containers I would always use a contiguous dynamic array.

Share this post


Link to post
Share on other sites
[quote name='darcmagik' timestamp='1318778039' post='4873132']
Thanks for the advice, I have implemented bubble sort many times in the past on arrays I haven't done so on a linked list maybe I will try that but I didn't bother at first because I know that bubble sort is one of the most inefficient sort routines available to choose. So I was looking for fast and efficient. All and all I feel confident with my abilities with linked lists( at least more than I was before I started this project). Now to take what I've learned and use it in my video game projects as needed.
[/quote]I strongly advise against that. Whilst bubblesort is easy to implement for an array, it is very very hard to implement for a linked-list. Merge Sort is far easier.

Insertion Sort is easy for a list though.

Share this post


Link to post
Share on other sites
[quote name='iMalc' timestamp='1318789715' post='4873178']
[quote name='darcmagik' timestamp='1318778039' post='4873132']
Thanks for the advice, I have implemented bubble sort many times in the past on arrays I haven't done so on a linked list maybe I will try that but I didn't bother at first because I know that bubble sort is one of the most inefficient sort routines available to choose. So I was looking for fast and efficient. All and all I feel confident with my abilities with linked lists( at least more than I was before I started this project). Now to take what I've learned and use it in my video game projects as needed.
[/quote]I strongly advise against that. Whilst bubblesort is easy to implement for an array, it is very very hard to implement for a linked-list. Merge Sort is far easier.

Insertion Sort is easy for a list though.
[/quote]

Writing a swap(a_prev, a_cur, b_prev, b_cur), extending the linked list by 1 in both directions (so header node, nodes, tail node), and bubble sorting from 2 to n-1 should make it a easier. (And trimming when you finish)


@alvaro
Thanks I need to check that out.

Share this post


Link to post
Share on other sites
[quote name='jameszhao00' timestamp='1318792265' post='4873189']
[quote name='iMalc' timestamp='1318789715' post='4873178']
[quote name='darcmagik' timestamp='1318778039' post='4873132']
Thanks for the advice, I have implemented bubble sort many times in the past on arrays I haven't done so on a linked list maybe I will try that but I didn't bother at first because I know that bubble sort is one of the most inefficient sort routines available to choose. So I was looking for fast and efficient. All and all I feel confident with my abilities with linked lists( at least more than I was before I started this project). Now to take what I've learned and use it in my video game projects as needed.
[/quote]I strongly advise against that. Whilst bubblesort is easy to implement for an array, it is very very hard to implement for a linked-list. Merge Sort is far easier.

Insertion Sort is easy for a list though.
[/quote]

Writing a swap(a_prev, a_cur, b_prev, b_cur), extending the linked list by 1 in both directions (so header node, nodes, tail node), and bubble sorting from 2 to n-1 should make it a easier. (And trimming when you finish)


@alvaro
Thanks I need to check that out.
[/quote]Adding a dummy node at the start can help (I personally use a clever trick that avoids this).
Adding one at the end only helps if you plan on doing exactly n passes through the list all the way from the start to the end every time. Normally bubble sort does a pass that is one shorter each time, but when it comes to doing it with a list you can have trouble with this moving end target.


Insertion Sort is the shortest algorithm for sorting a linked-list. I thoroughly recommend it.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this