Sorting Linked lists

[willisoften]

Java assignment is due in a couple of weeks.

 

All is well apart from the last part sort the linked list.

 

The list is a singly linked list consisting of nodes which contain a student record and the ref to the next node.

 

The student record holds the properties belonging to each student.

 

The list itself has to be sorted by Student ID (an integer) held in Student Record.

 

 

Sounds simple but it's driving me up the walls!!

 

Is there something I need to know which makes sorting linked lists so much more difficult than sorting arrays?

 

I was trying a merge sort,

any comments?

 

All help, sympathy or money gratefully accepted.....

[fuzzylizard]

The easy way to sort a linked list is to put it into an array, sort the array and then recreate the list. However, some people may think this is cheating.

 

The trick to sorting a linked list is the amount of pointers (or references) you place in the list. Remember, you always have to keep one reference pointing at the head of the list. This can not be moved or you are toast. Therefore, you need to create a whole bunch of other pointers that will sort the list.

 

If you were doing a bubble sort (it easy to illustrate) you would need two references for the list in addition to the head reference. These two pointers would then repeatedly traverse the list changing the position of any nodes it finds that needs to be sorted.

 

For more complex sorts you will need more references. Try not to think about the list as a whole, but the list as it exists at the points where your references are pointing. Therefore, if you need to see more of the list, you need to create more references.

 

Make sense???

 

Addendum: You need to find yourself a good book on Algorithms and Patterns in Object Oriented Programming aimed specifically at Java. If you can find the right book, it will have the algorithms you need as they relate to a linked list.

Edited November 19, 2003 by fuzzylizard

[Cannonfodder]

One idea is to build a new linked list that co-exists with the original list. The original isn't touched. The new linked list will be sorted. This list will consist totally of pointer objects.

 

Some sort algorithms you can take a google peek at are btree or quicksort. quicksort is supposely one of the fastest sort algorithms. Be a good exercise for you to learn how to use it.

 

Now that I'm thinking about this. A sort pointer node would consist of

 

dataptr

lesserPtr

greaterPtr

 

dataptr would point to the actual data.

 

lesserPtr would point to a node that contains data that sorts lesser than the current nodes data.

 

greaterptr would point to a node that contains data that sorts greater than the current nodes data.

 

Once the tree is built, you can retrieve the sorted data by following a lessPtr to the end and then follow the greaterptr.

 

Draw it on paper..

 

If you haven't already, you should look at the concept of recursion. Recursion is when a method calls itself until some condition is met. Recursion and linked lists go hand in hand like butter on toast. They are very useful for traversing linked list since you are basically passing pointer values and continuing until you hit a NULL pointer.

 

Ask questions if you are not getting this..

[tyme]

in a linked list sorting is easier because instead of changing out spots like in an array (where you need a temp) you just have to re-order the linked list, that is, change where each one links to so that it goes to the next one in the order you specify.

 

but be sure that when you have "current", "next", and "previous" because if you change it up you have to have "previous" point to "next" and then "next" to "current" if you know what i mean...

 

ok, i think i managed to confuse myself but i know what i wanted to say and i think it came out right....i could explain better if i had one of my old C++ programs in front of me.

[willisoften]

Yes I need to take a more planned approach to this rather than my usual change it and see-what-happens approach.

 

Thanks for the ideas.

 

If I can't work it out I'll hand in what I can do and get it marked out of 85. So it's not the end of the world. It's just that I'm stubborn and can't leave it alone!

[tyme]

if i could remember the syntax of linked lists i could better explain with a code example, but i don't remember the syntax. i can see how to do it in my mind (amazing, eh?) but I don't know how to explain it without showing it in code...

[Cannonfodder]

Try sitting down with a piece of paper and a bunch of random single letters. Then make a circle for the first one. That's the head of the list. Let's say its an M. Then grab the next letter, an L. L is less than M so the next node you create is under M and pointed too by the lesserPtr (left side).

 

The next letter is P. You start at the head of the tree (M). Is greater than M, so you point M's greaterPtr at P. At this point yoiu should have a 3 node tree. M on top and L to the left and P to the right. Looks like a tree.

 

Now add O. Start with M. O > M right. Follow tree down one on right. O < P. Since P's lesserPtr is NULL, make a new node and point P.lesserPtr at it.

 

If you play with this, the rules are

 

start at the top

follow down, going left or right (lesser or greater) until you hit the end of a branch.

 

When you are done, you are sorted..

 

Now retrieve sort. Start at top and go lesserPtr as far as you can go. When you hit NULL in the lesserPtr, you have your first entry. Now backup one ptr. Go right (greater) and then go left again until you hit null. Just repeat that pattern and the retrieved entries should be sorted.

 

Here is an example of recursion..

 

function travelTree(pointer myPtr)
 if myPtr.lesserPtr = NULL
    print(myPtr.dataPtr.value)
 else
   travelTree(myPtr.lesserPtr)
   * Now do right pointer
   travelTree(myPtr.greaterPtr)
 end
endfunc

 

If you sit with paper and follow this through, you will see that on traveling down a tree on the left (lesser), it keeps calling itself and passing in the lesserptr for the current node until it hits NULL. At this point you have a stack of function calls placed one on top of another like a stack of plates. When it reaches the bottom and prints the value, it will then start returning to the prior calls and each time will execute the next call passing in the greaterPtr.

 

It's a bit tricky conceptually. Just gotta slow down and sketch it on paper conceptually and once you get the rules it will become easy to program.

[willisoften]

OK Cheating or not I think I'm going for the array solution.

Simply because this is the one I think I can do myself.

 

Question:

 

Node[] n_array = new Node[list.length];
   for (int x=0;x<list.length;x++)
   {
     n_array[x]= nodeAt(index); 
     //nodeAt() method for refering to node at list position
   }

 

This isn't so much the code as the general idea.

 

Is this an array filled with copies of the nodes or an array of reference variables (pointers)?

 

I was rather hoping it was the latter!

 

Addendum: You need to find yourself a good book on Algorithms and Patterns in Object Oriented Programming aimed specifically at Java. If you can find the right book, it will have the algorithms you need as they relate to a linked list.

 

I've got a course text book which covers sorting and linked lists in two different sections the section on sorting lists actually jumps to trees (surely would make more sense?) but thats outside the assignment specification.

 

I've found this particular module extremely difficult. Both lecturers are Chinese and although they really seem to know their stuff they both speak heavily accented English. I sit near the front and still can't make out much of whats said.

Complaints have been made at student staff committees then ignored by those in authority. I don't want to give anyone making a living a hard time but it is very frustrating.

Edited November 20, 2003 by willisoften

[ShadowFoxLSU]

This is a standard C link list sorting function I wrote a couple of years ago, feel free to modify to your needs:

 

void sort (ptr pntr)

/*

Function: Sorts the link-list

Input: pointer for the link list

Output: none

*/

{

int id; /*declaring vars */

char name [20];

int years;

int product;

ptr cur, org;

cur = pntr;

org = pntr;

while (cur != NULL) /* Going through link list */

{

if( cur->id < org ->id)

org = cur;

cur= cur->nextptr;

}

if(org != pntr) /* swapping if nessecary */

{

id = pntr->id;

pntr-> id = org->id;

org->id = id;

strcpy(name, pntr->name);

strcpy(pntr->name,org->name);

strcpy(org->name, name);

years= pntr->years;

pntr->years = org->years;

org->years = years;

product= pntr->product;

pntr->product = org->product;

org->product = product;

}

if(pntr->nextptr != NULL) /* if not end of LL, call again */

sort(pntr->nextptr);

}

[willisoften]

Thanks to all. I do now have a sorted linked list.

 

Create an array of nodes

Sort node array according to Student Id Number

reset "next" for each node.

    public void sortRecords()
 {
 //Create array of references
   Node[] noddy = new Node[length];
   for (int x=0;x<length;x++)
   {
     noddy[x]= nodeAt(x);
   }
   
//sort references by Student ID
//mergeSort is too long to reproduce in this post
    mergeSort(noddy);


//reset "next" in each Node    
   Node p = head;
   
   for (int i=0;i<noddy.length;i++ )
   {
     p.setNext(noddy[i]);
     
     //move to next node in list
     p = p.getNext();
   }

  
}//Ends sortRecords

 

greyfoxlsu: thanks for maiking your code available I will examine it when I have more time. Unfortunately 3 assignments due by 28th this month. This is the most difficult.

[Cannonfodder]

See? We don't need no stinking arrays !

 

I hear you on the foreign language teachers. It sucks! I tried to take lisp once with a teacher from Pakistan. Between his accent and my hearing loss, it was a no go furious3

[willisoften]

See? We don't need no stinking arrays ! 

 

I hear you on the foreign language teachers. It sucks! I tried to take lisp once with a teacher from Pakistan. Between his accent and my hearing loss, it was a no go  furious3

I have tinitus (how do you spell it) and otherwise dull hearing from operating woodworking machinery without ear protection. It was provided but I was 17 and obviously really macho (read stupid).

 

Amazing how often one is mistaken for the other amongst young men.

 

I usually get along ok in conversation (I think I've got good at guessing what people are saying) but background noise and distance from the speaker make a big difference. When someone enunciates words differently, compared to what I'm used to I'm completely lost.

 

It's a strange state of affairs when I get more help and feedback from this forum than from the people who are taking my tuition fees.

[ShadowFoxLSU]

Technically, a link list is a dynamic array. You can sort it using a stardard array, but at least for me my teachers through a shit fit (heck, my teachers through a shit fit when I used advanced techniques (read classes and trees). Will I would ask your teacher about using a static array (yea, I know it is somewhat dynamic with the max size being a var, but an array of set size is 'static'). You dont want to get one of those catch 22 things.

[Cannonfodder]

These new digital hearing aids make all the difference here. I have like a 70% hearing loss and they do wonders. Doesn't take much to lose it though due to background. Good luck with your pointers.. :)