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:

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?

Which one are you doing?
1. Sorting as you insert a new item. (more common)
2. Sorting already inserted items.

Post some pseudo-code (i.e. plain english) of how you think the process should go, and we'll gladly help clear up misconception.

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

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

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.

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

I like to use a bubblesort type method for sorting a linked list.. kinda like how you would for an array.

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

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:

the performance may be hideous but it's easy to code