Sorting a Linked List
I am trying to write a program that sorts a link list, and I can't get it to work. Could somebody tell me what I am doing wrong? The psedocode for the sort is:
while (the first list still contains nodes)
{ 1. Find the node that contains the largest item of all the nodes in the
first list.
2. Remove the largest node from the first list.
3. Putthis node at the beginning of the second list.
(
This is the code I have:
publicstatic IntNode linkedLlistSort (IntNode head)
{
IntNode node = null, tail =null;
while (head.getLink()!=null)
{
node = head.findMax(head);
node = node.link;
head = node;
}
return head;
}
privatestatic IntNode findMax(IntNode head)
{
for (IntNode cursor = head; cursor.getLink()!=null; cursor = cursor.getLink())
{
if (head.getLink().getData() < cursor.getLink().getData())
head = cursor;
}
return head;
}
My first question is: what is IntNode? For my further explanation I assume it to be something like:
class IntNode {
int data;
IntNode link;
public int getData() { return data; }
public int getLink() { return link; }
}
So, what your findMax(head) does is to search the node whose linked node has the largest data beginning with the given head node. Note, that head not necessarily is the beginning of a linked list of nodes!
In linkedListSort(head) you start out with the given head node. You then search for a node following the links, which has a linked node having the largest data (using findMax). You then assign the linked node (i.e., the node having the largest data) to node and to head and proceed to search for the next maximum node from the found maximum one.
To illustrate, what your program does, lets say, the following represents the chain of nodes starting from head:
head -> 1 -> 5 -> 2 -> 4 -> 3
after the first loop in linkedListSort you would receive:
node -> 5 -> 2 -> 4 -> 3
head -> 5 -> 2 -> 4 -> 3
after the second loop:
node -> 4 -> 3
head -> 4 -> 3
after the third and last loop:
node -> 3
head -> 3
Where node has no further link and head will be returned.
You neither unlink or relink anything but travel from one large node to the next one. If you revisit your intention, you can easily see, that it does neither of the 3 points. To accomplish this, you will have to:
1. Keep the first node of the list as starting point for searching for maximum data unchanged,
2. Link the precessor of the maximum to the successor of it, and
3. Link the maximum to the tail of a new list, where:
3.a) If you do not have a new list, you take the maximum as head node (which you keep unchanged), and
3.b) Keep the maximum as tail node
4. Return the head of the new list.
Cheers,
Stefan
So the problem with my program is findMax() ? Or is it how I use findMax() in the sort? Which method do I need to fix? I'm sorry, this program is just really confusing me.
I tried to do what was suggested, but I still can't seem to get it to work. Can anybody else help me? Any help would be greatly appreciated!
This is the sort method I now have:
public static IntNode linkedListSort (IntNode head)
{
IntNode node = null, tail = null;
while (head.getLink()!= null)
{
IntNode max = findMax(head);
max = max.getLink();
max = tail;
if (node == null)
{
max = node;
}
else
{
max = tail;
tail = head;
}
node = node.link;
}
return node;
Well, I tried to describe the problem and a how to, because there are thousands of books and lectures and tutorials out there on how to build a sort, and I assume you are about to learn how to realize sorting and not only using it. In the latter case, you could simply use LinkedList and Collections.sort().
As I wrote, your max-search is ok. You will find the predecessor of the maximum data container within your list, which you need, because you have to rechain it in your algorithm. The main part would be something like this (despite null checks and initialization issues):
predecessorOfMax = findMax(originalHead);
sortedTail.link = predecessorOfMax.link;
predecessorOfMax.link = predecessorOfMax.link.link;
sortedTail = sortedTail.link;
Of course, sorting the way you do is not optimal. For a more efficient algorithm use google searching for "mergesort".
can't you just use the Collections Class to do the sort for youjava.utils.Collections.sort( yourList, listComparator);where listComparator is a Comparator on your list contents
Hello!Using Collections.sort() with a linked list won't be very efficient. Then again, linked lists aren't well suited for sorting at all. OP, why is it you insist on a linked list?And I agree with stefan.Yours, Ole
OleVVa at 2007-7-14 22:38:05 >
