sorting link list

**laserlight** · 11-30-2008, 01:55 PM

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.

MK27 · 11-30-2008, 01:59 PM

Quote:

Originally Posted by laserlight

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?

**laserlight** · 11-30-2008, 02:05 PM

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.

MK27 · 12-02-2008, 12:15 PM

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.

**laserlight** · 12-02-2008, 12:50 PM

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.

MK27 · 12-02-2008, 01:25 PM

Quote:

Originally Posted by laserlight

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.

Quote:

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

**laserlight** · 12-02-2008, 03:01 PM

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.

MK27 · 12-02-2008, 05:47 PM

Quote:

Originally Posted by laserlight

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.

12-02-2008, 12:15 PM	#19
MK27 subminimalist Join Date: Jul 2008 Location: NYC Posts: 3,944	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(msizeof(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(lensizeofretlist))==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. __________________ Accuracy and integrity mean nothing if you don't make it past the censors...PYTHAGORAS Last edited by MK27; 12-02-2008 at 02:49 PM.
MK27 is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
reading data from a file - link list	peter_hii	C++ Programming	7	10-25-2006 09:11 AM
airport Log program using 3D linked List : problem reading from file	gemini_shooter	C Programming	3	03-04-2005 02:46 PM
compiler build error	KristTlove	C++ Programming	2	11-30-2003 10:16 AM
1st Class LIST ADT	Unregistered	C++ Programming	1	11-09-2001 07:29 PM
singly linked list	clarinetster	C Programming	2	08-26-2001 10:21 PM