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.Originally Posted by MK27
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.Originally Posted by MK27
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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
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.Originally Posted by MK27
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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:
The two functions are:Code:struct nodeptr { struct _node *np; };
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: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; }
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
I do not understand what you mean by this.Originally Posted by MK27
Neither does merge sort require a temporary linked list, as mentioned in that article that I linked to.Originally Posted by MK27
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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.
Have you done it that way? My reading of the article includes this:Neither does merge sort require a temporary linked list, as mentioned in that article that I linked to.
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
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?Originally Posted by MK27
No, but Simon Tatham's own example in C appears to do so.Originally Posted by MK27
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.Originally Posted by MK27
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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