sorting linked list using link manipulation

This is a discussion on sorting linked list using link manipulation within the C Programming forums, part of the General Programming Boards category; Hi, I am stuck at a peculiar problem where in there is a linked list and it has to be ...

  1. #1
    Registered User
    Join Date
    Jun 2009
    Location
    US of A
    Posts
    305

    sorting linked list using link manipulation

    Hi,

    I am stuck at a peculiar problem where in there is a linked list and it has to be sorted out using the link part. Can anyone tell the tips to understand it (if it is desired i can post the entire code here) but how do i understand it because i seem to get lost at one or the other part. (Have spend a couple of hours trying to figure out the logic behind its steps). Please give some suggestions.

    I mean if you were to encounter a complex problem how would you proceed to understand it?

  2. #2
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,246
    Well the simplest way is to sort the list the same way you would sort an array.

    Iterate through the list starting from the beginning, and find the node that has the lowest value. Once you have found that node, place it at the beginning of the list. Now iterate through starting at the second node (the one after the one you just moved to the beginning of the list). Do the same thing: find the node with the lowest value, and place it after the first node you moved to the beginning. Keep going until the list is sorted. This is just a bubble sort for linked lists.

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    I'm not sure where you were going with "has to be sorted out using the link part". Surely you can't mean that you are sorting by the values of the links, because that makes no sense. Do you mean sorting only by switching links, or sorting without switching links, or what?

  4. #4
    Registered User
    Join Date
    Jun 2009
    Location
    US of A
    Posts
    305
    yes i mean sorting by switching links

    [insert]
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct node{
    
    	int data;
    	struct node *link;
    };
    
    void getdata();
    void display(struct node *);
    void selection_sort();
    struct node *start;
    
    int main(void){
    
    	start = NULL;
    	getdata();
    	display(start);
    	
    	selection_sort();
    	display(start);
    
    	return 0;
    }
    
    void selection_sort()
    {
    	struct node *p, *q, *r, *s;
    	p = start;
    	r = start;
    	q = p ->link;
    	s = q;
    
    	// nodes being compared are adjacent and p is first node
    	while(p ->link != NULL)
    	{
    		s = q = p->link;
    
    		while(q != NULL)
    		{
    			if( p == start && p ->link == q)
    			{
    				if(p ->data > q ->data)
    				{
    					struct node *temp;
    					temp = p ->link;
    					p->link = q->link;
    					q ->link = temp;
    					q = p->link;
    					s = p;
    					p = r = q;
    				}
    			}
    			else if( p == start && p ->link != q)
    			{
    				if(p ->data > q ->data)
    				{
    					struct node *temp;
    					temp = p->link;
    					p ->link = q ->link;
    					q ->link = s;
    					s ->link = p;
    					q = r->link;
    					s = p;
    					p = r = q;
    					start = p;
    				}
    			}
    			else if(p != start && p->link == q)
    			{
    				if(p ->data > q ->data)
    				{
    					struct node *temp1, *temp2;
    					temp1 = q->link;
    					temp2 = p->link;
    					p->link = q->link;
    					q ->link = temp2;
    					r->link = q;
    					q = temp1;
    					p = r->link;
    					s = p ->link;
    				}
    			}
    			else if(p != start && p->link != q)
    			{
    				if(p ->data > q->data)
    				{
    					struct node *temp1, *temp2;
    					temp1 = p->link;
    					temp2 = q->link;
    					p ->link = q->link;
    					q ->link = s;
    					s ->link = p;
    					r ->link = q;
    					p = q;
    					s = q;
    					q = temp2;
    				}
    			}
    			s = q;
    			q = q->link;
    		}
    
    		r = p;
    		p = p->link;
    	}
    }
    
    void getdata(){
    	
    	struct node *p, *q;
    	char ch;
    	int val;
    	do{
    		
    		printf("\nEnter data for the list");
    		scanf("%d", &val);;
    
    		// adding the node for the first time
    		if( start == NULL)
    		{
    			p = malloc(sizeof(struct node));
    			p ->data = val;
    			p ->link = NULL;
    			start = p;
    		}
    		else
    		{
    			p = start;
    			while(p ->link !=  NULL)
    				p = p ->link;
    			q = malloc(sizeof(struct node));
    			q ->data = val;
    			q ->link = NULL;
    			p ->link = q;
    		}
    	
    		printf("\nAny more data");
    		ch = getche();
    	}while (ch == 'y' || ch == 'Y');
    }
    
    void display(struct node *p){
    	
    	struct node *temp;
    	temp = p;
    	while(temp != NULL){
    		printf("\n%d", temp->data);
    		temp = temp->link;
    	}
    }
    I am getting errors but now i am totally lost in this :-(

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Well then there's two parts to the problem, I guess: (1) figuring out how to switch links and (2) deciding which elements of the list to switch. To figure out 1 you should draw some pictures. For number 2 you just need to decide what sort of sorting algorithm you want to use -- bubble sort isn't bad, unless your list is very long; and having two consecutive elements of the list makes doing part #1 slightly easier, I think.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Quote Originally Posted by bithub View Post
    Well the simplest way is to sort the list the same way you would sort an array.

    Iterate through the list starting from the beginning, and find the node that has the lowest value. Once you have found that node, place it at the beginning of the list. Now iterate through starting at the second node (the one after the one you just moved to the beginning of the list). Do the same thing: find the node with the lowest value, and place it after the first node you moved to the beginning. Keep going until the list is sorted. This is just a bubble sort for linked lists.
    Nope you're describing "Selection Sort". Bubble Sort only ever swaps adjacent items.

    Trying to "sort the list the same way you would sort an array" is not good. You get neither random access nor the ability to insert/remove in constant time. All good algorithms are therefore out, and anything that is left tends to suck.

    By far the easiest and simplest way to sort a list is using Insertion Sort. But if you're comfortable with recursion then MergeSort isn't all that hard and gives much better performance.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Jun 2009
    Location
    US of A
    Posts
    305
    @Malc

    I like the eternally confuzzled funda that is presented on one of the webpages. I think its a perfect word describing the state i am currently in.

  8. #8
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    Quote Originally Posted by roaan View Post
    Hi,

    I mean if you were to encounter a complex problem how would you proceed to understand it?
    rooan, as tabstop suggested, draw pictures and code from that. Attached is my attempt to sort in ascending order. Neatness does not count.

    Once you get the general case, as I have in the picture, then work on the special cases like:
    What if pLargest is the first element pointed at by root?
    What if root points to a list with only 1 element or no elements?

    A picture that you animate with pencil and eraser will help to bring out the special cases.

    I don't know about the code you posted. If you're lost, in it, then its time to scrap it and start over.

    I hope that helps you.
    Attached Images Attached Images

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by roaan View Post
    Hi,

    I mean if you were to encounter a complex problem how would you proceed to understand it?
    First, for tough problems, back away from the keyboard! How would you swap a tiny linked list by hand (pencil and paper)?

    Write that out, step by step, and I recommend selection sort, not bubble sort or any others, for now. Selection sort combines simplicity and efficiency rather well.

    In this process, you want to break down the big problem, into small "chunks" that you can first solve, by hand.

    Write down each small "chunk" that you need. Clearly, you'll need a "chunk" to swap two nodes in your linked list.

    Those "chunks" will become either blocks of code, or functions in your program, later on.

    Once you get a very small linked list of 3 nodes to work right by hand, then you can make that the basis for your program.

    I would describe this process as breaking down the problem into it's smaller constituent parts, until each part can be understood. Then build these parts back up, using paper and pencil if needed, while you learn "the game" (what the problem is all about).

    Don't expect to know the game well, until you know the basic rules and techniques, used. Here, that would be 1) How to swap nodes in a linked list and 2) How to code a selection sort for that list.

    Avoid like hell itself, the naturally tendency to start banging away "something" on the keyboard, getting all these lines of code, and having no real understanding why it doesn't work. That's only human perhaps, but it's *definitely* something to be avoided.

  10. #10
    Registered User
    Join Date
    Jun 2009
    Location
    US of A
    Posts
    305
    @all

    Thanks a lot !!!!!!!!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  2. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 12:21 PM
  3. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 05:40 PM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 08:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21