# Sorting A Linked List

• 10-14-2004
Proggy1
Sorting A Linked List
Hi, is any one able to give me a start as to how to sort (descending by age) a linked list. I have been working on this now for about a week, and still have problems understanding how to go about switching the nodes around.

Any help is appreciated!!

Thanks!!

Proggy :cool:
• 10-14-2004
kermi3
I realize this isn't your intention, but people will not be receptive to your question if they think you want them to do all of the work.

What are your thoughts so far? Can you be a bit more specific about where you are confused? What method have you been thinking about using?
• 10-14-2004
alphaoide
Which one are you doing?
1. Sorting as you insert a new item. (more common)
2. Sorting already inserted items.
• 10-14-2004
Zach L.
Post some pseudo-code (i.e. plain english) of how you think the process should go, and we'll gladly help clear up misconception.
• 10-15-2004
arian
if u want to Sort already inserted items (u have an unsorted linked list) choose a sorting methode and use it for the part of nodes that u want the linked list become sorted by( at ur message u have wroten 'AGE') .
for example:
Code:

``` if (node1->age<node2->age) {........   ........           }```
then if it is necessary to chage the place , just change the values in the 2 nodes , dont chane the pointers .

and if u want to sort a linked list while u r creating it do these steps
1- create a new node that u want to insert it to linked list .
2-compare new node with the first node , if new node is bigger go to 4 and else go to 3 .
3-insert new node before the firt node and go to 1.
4-compare new node with 2nd node ,if new node is bigger do this step for 3th node and ......
when u find a node that is bigger than new node , insert the new node before it .

hope it helps
• 10-15-2004
CornedBee
If the held objects are large or complicated to copy, changing the pointers could be more efficient.
• 10-16-2004
quzah
Quote:

Originally Posted by CornedBee
If the held objects are large or complicated to copy, changing the pointers could be more efficient.

I don't see the point in using a linked list if you're going to not use them correctly. There's never any need to move the contents of a node to another node. Just realign pointers. What's the point of using identical containers to store an item, if you're just going to move it to a different container? Just change the position of the containers in the list.

Quzah.
• 10-16-2004
Salem
> and still have problems understanding how to go about switching the nodes around.
Draw a list out on paper, with lots of lines between nodes representing the links between nodes.

Then draw the list again with two nodes swapped and see how all the links change.

When you understand that, do what your diagrams do in code.
• 10-16-2004
The Brain
I like to use a bubblesort type method for sorting a linked list.. kinda like how you would for an array.
• 10-17-2004
Prelude
>I like to use a bubblesort type method for sorting a linked list..
Why? Bubble sort is bad enough for arrays. It's hideous for linked lists. If you want a simple linked list sort then the insertion sort algorithm is probably the best. For performance, merge sort is what I usually go with.
• 10-17-2004
Proggy1
Am I on the rigth track???
I am doing the sorting when inserting a new item. So far I am trying to do it with a "while" and then a nested if. Looks something like this:

Code:

```        if (temp->nxt == NULL)         {                 cout << "List sorted according to age!" << endl;         }         else         {                 temp = start_ptr;                 while (temp->nxt != NULL)                 {                         if (temp->age > temp->nxt->age)                         {                                 temp2 = temp->nxt;                                 temp->nxt = temp;                                 temp = temp2;                                 start_ptr = temp;                         }                         else                                 cout << "List sorted according to age!" << endl;                 }         }```
Am I on the rigth track????

Cheers,

Proggy :cool:
• 10-18-2004
The Brain
the performance may be hideous but it's easy to code