Thread: sorting link list

  1. #16
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MK27
    I will have to investigate this "Merge Sort".

    I suppose that since modern computers have so much memory in relation to their processing power, my contention that that the bubble sort saves space may be almost mute.
    When you investigate merge sort, you will find that space consumption is a disadvantage, but not where linked lists are concerned. Consequently, any argument about saving space just falls flat.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  2. #17
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    When you investigate merge sort, you will find that space consumption is a disadvantage, but not where linked lists are concerned. Consequently, any argument about saving space just falls flat.
    So...rather than rewrite the linked-list out into fresh halfs, I could just use a counter to work with a half at a time?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #18
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MK27
    So...rather than rewrite the linked-list out into fresh halfs, I could just use a counter to work with a half at a time?
    I am not sure what you mean by a counter. Fundamentally, I suspect that you are thinking of a linked list as an indexed array, but as iMalc mentioned, if you want to use a linked list, you might as well take advantage of its nature as a linked list. A quick search for "linked list merge sort" brings up Mergesort For Linked Lists, apparently by the same guy responsible for PuTTY.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #19
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Whew! I got the merge sort, and I'd love it if someone could glance throught the code to see if they can spot something less than praise worthy. It will work with the above script but because it can't be done without creating some kind of additional list, and I couldn't get a plain array o' struct pointers to work for me when passed aroundf, you need to add:
    Code:
    struct nodeptr {
    	struct _node *np;
    };
    The two functions are:
    Code:
    int LLsplitsort (struct nodeptr *retlist, struct nodeptr *left, int Llen, struct nodeptr *right, int Rlen) {
    	int i=0, LC=0, RC=0;
    	while ((Llen>LC) && (Rlen>RC)) {
    		if (comparenames(left[LC].np->name,right[RC].np->name)==1) {
    			retlist[i].np=left[LC].np;
    			LC++;}
    		else { 
    			retlist[i].np=right[RC].np;
    			RC++;}
    		i++;
    	}
    	while (Llen>LC) {retlist[i].np=left[LC].np;i++;LC++;}
    	while (Rlen>RC) {retlist[i].np=right[RC].np;i++;RC++;}
    	return 0;
    }
    		
    int LLmergesort (struct nodeptr *retlist, node *head, int len, int tag) {
    	int i, m=len/2, R=m, retv;
    	node *middle, *now, *start=head;
    	struct nodeptr *left, *right;
    	if ((left=malloc(m*sizeof(*left)))==NULL) return -1; 
    	if ((right=malloc((m+1)*sizeof(*right)))==NULL) return -1; 
    	
            if (tag==0) {		// first iteration
    		head=head->next;	//uses an empty head	 
    		if ((retlist=malloc(len*sizeof*retlist))==NULL) return -1;
    	}
    	tag++;
    	
            if (len==1) return tag;		// depth of error
    	if (len%2>0) R++;
    	now=head;	
    	if (len<4) middle=head->next;
    	else for (i=0;i<=m;i++) {
    		middle=now;
    		now=now->next;
    	}
    	
    	if (m==1) left[0].np=head;
    	else if ((retv=LLmergesort(left,head,m,tag))!=0) return retv;				
    	if (R==1) right[0].np=middle;
    	else if ((retv=LLmergesort (right,middle,R,tag))!=0) return retv;	
    	LLsplitsort (retlist,left,m,right,R);
    	free(left);
    	free(right);
    	
            if (--tag==0) {				// THE END
    		start->next=retlist[0].np;
    		for (i=0;i<len-1;i++) retlist[i].np->next=retlist[i+1].np;
    		free(retlist);
    	}
    	return 0;
    }
    LLsplitsort is called by LLmergesort. Because of the recursion, the first argument to LLmergesort should be set to NULL when first called and the last to 0. If there is an error, it returns -1 for malloc failure or >0 to indicate the depth of a technical mistake, so:

    if ((tmp=LLmergesort(NULL,head,num,0))!=0) printf("!! LLmergesort() error at depth %d...\n",tmp);

    My result was correctly sorted and made 32 comparisons (13 elements). The same list bubble sorted made 130 comparisons, and assembled with the insertion sort above, 39 comparisons. However, the insertion sort seems kind of better since it builds the list from empty (merge sort just sorts) and doesn't require a temp list while sorting. If I can think of some more names I will try it with a greater number of elements and see what's up.

    Last edited by MK27; 12-02-2008 at 02:49 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #20
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MK27
    However, the insertion sort seems kind of better since it builds the list from empty (merge sort just sorts)
    I do not understand what you mean by this.

    Quote Originally Posted by MK27
    and doesn't require a temp list while sorting.
    Neither does merge sort require a temporary linked list, as mentioned in that article that I linked to.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #21
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    I do not understand what you mean by this.
    I mean that the insertion sort will be better if the list is already sorted and you are adding a new element, so if you have an empty list, it might be better to add them one at a time with the insertion sort than to just make a list and merge sort it, because the merge sort is kind of overkill for adding one element.

    Neither does merge sort require a temporary linked list, as mentioned in that article that I linked to.
    Have you done it that way? My reading of the article includes this:

    In each pass, we are merging lists of size K into lists of size 2K. (Initially K equals 1.) So we start by pointing a temporary pointer p at the head of the list, and also preparing an empty list L which we will add elements to the end of as we finish dealing with them. Then:

    I did try it without one, but if you look at the nature of the recursion I think it will be impossible. Watch what happens if you try changing any of the pointers before the sort is complete! However, you don't need to make two linked lists; you just need an array with the pointers in the proper order. Which is to say I didn't use a temporary linked list, I used a temporary list (array).

    edit: But at 17 names, the insert/build does 70 comparisons while the build then merge sort only does 51...
    edit: at 21 names, the difference is 117 to 71 (poor ol' Bubble Sort is now 357)...god this fun
    Last edited by MK27; 12-02-2008 at 01:45 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #22
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MK27
    I mean that the insertion sort will be better if the list is already sorted and you are adding a new element, so if you have an empty list, it might be better to add them one at a time with the insertion sort than to just make a list and merge sort it, because the merge sort is kind of overkill for adding one element.
    Yes, merge sort is overkill for adding one element, but your reasoning is that because merge sort is overkill for adding one element, it must be overkill for adding n elements. Consider the same argument for an array: if you are adding a single element to a sorted array, quick sort is overkill; bubble sort could well be the best. Based on this, would you conclude that bubble sort is generally better (as in more efficient) than quick sort?

    Quote Originally Posted by MK27
    Have you done it that way?
    No, but Simon Tatham's own example in C appears to do so.

    Quote Originally Posted by MK27
    So we start by pointing a temporary pointer p at the head of the list, and also preparing an empty list L which we will add elements to the end of as we finish dealing with them.
    L is not a temporary linked list in the sense that it points to a new list of elements. Rather, it consists of two pointers, the head and tail of the linked list of elements that have been dealt with. This is why the space consumption is constant, not proportional to the size of the linked list as you implemented it.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #23
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    No, but Simon Tatham's own example in C appears to do so.
    Maybe. I actually didn't want to look at it first, but I will concede that Simon perhaps did somewhat of a better job.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. reading data from a file - link list
    By peter_hii in forum C++ Programming
    Replies: 7
    Last Post: 10-25-2006, 09:11 AM
  2. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  3. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 10:16 AM
  4. 1st Class LIST ADT
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 11-09-2001, 07:29 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

Tags for this Thread