Thread: Sorting A Linked List

  1. #1
    Registered User
    Join Date
    Oct 2004
    Posts
    2

    Question 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

  2. #2
    Lead Moderator kermi3's Avatar
    Join Date
    Aug 1998
    Posts
    2,595
    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?
    Kermi3

    If you're new to the boards, welcome and reading this will help you get started.
    Information on code tags may be found here

    - Sandlot is the highest form of sport.

  3. #3
    unleashed alphaoide's Avatar
    Join Date
    Sep 2003
    Posts
    696
    Which one are you doing?
    1. Sorting as you insert a new item. (more common)
    2. Sorting already inserted items.
    source: compsci textbooks, cboard.cprogramming.com, world wide web, common sense

  4. #4
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Post some pseudo-code (i.e. plain english) of how you think the process should go, and we'll gladly help clear up misconception.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  5. #5
    Registered User
    Join Date
    Nov 2003
    Posts
    183
    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

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    If the held objects are large or complicated to copy, changing the pointers could be more efficient.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  9. #9
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    I like to use a bubblesort type method for sorting a linked list.. kinda like how you would for an array.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  10. #10
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

  11. #11
    Registered User
    Join Date
    Oct 2004
    Posts
    2

    Exclamation 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
    Last edited by Proggy1; 10-17-2004 at 07:36 PM.

  12. #12
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    the performance may be hideous but it's easy to code
    Last edited by The Brain; 10-18-2004 at 12:57 AM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 07:47 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM