insertion sort in doubly linked list

[farhanakram]

i have written following insertion sort program for a doubly linked list completely by myself.The the sort function is giving me Segmentation error and i am unable to figure it out...Plz help me out and forgive me if the code is too wrong to handle..

//insertion sort using doubly linked list
//the sort function is taking &head as argument.
//if anyone has a simpler algo,please let me know

void sort(node **q)
{
	int n=0;
	node *cur;
	cur=*q;
	if (cur->next==NULL) //there is only one element in list
		return;
	
	node *end,*tmp;

	while(cur->next!=NULL)
		cur=cur->next; //reach the last node

	while(cur->prev!=NULL)
	{
		end=cur;
		tmp=cur->prev;
		cur=cur->prev;

		while(tmp!=NULL && tmp->data>=end->data) //comparison starts here
		{
			tmp=tmp->prev;
			n++;
		}
		if (n)
		{
			if (tmp==NULL) //currently compared node is smallest
			{
				tmp=*q;
				end->prev=NULL;
				end->next=tmp;
				end->next->prev=end;
				*q=end;
			}
			else
			{ //currently compared node should lie in between somewhere in sorted list
				tmp->prev->next=end;
				end->prev=tmp->prev;
				tmp->prev=end;
				end->next=tmp;
			}
			cur->next=NULL; //making the next pointer on node previous to currently compared node as NULL 
		}
	}
}

[zeroliken]

Try to check / test first / (temporarily remove) each statement in the function to pinpoint which line causes the program to give a segmentation fault

either that or post the complete program

[rubberman]

1. Test that the incoming node** q argument is not null.
2. Test that after assigning *q to cur, that cur is not null.
3. Test that the data element in the nodes you are comparing is not null.
4. Simplify, simplify, simplify.

[Trentacle]

Have you noticed that n is only ever zero at the beginning of the program? I'm not 100% sure I understand the purpose of it, but I think you should at least reset it on each iteration of the while loop.

Furthermore, what happens when tmp ends up pointing to the head of the list? tmp isn't NULL, but tmp->prev is... that could be the cause of your segfault.

However, this is kind of convoluted for an insertion sort. Consider rewriting it.

[farhanakram]

Thanx for the replies.i found out that the value of n was not initialised to zero for every iteration.Moreover, the segmentation fault was removed and the function was modified as there were some problems in my algoriths.Here is the correct sort program:

void sort(node **q)
{
	int n;
	node *cur;
	cur=*q;
	if (cur->next==NULL)
		return;
	
	node *ptr,*tmp;
	cur=cur->next;

	while(cur!=NULL)
	{
		n=0;
		ptr=cur;
		tmp=cur->prev;
		cur=cur->next;

		while (tmp!=NULL && tmp->data>ptr->data)
		{
			n++;
			tmp=tmp->prev;
		}

		if (n)
		{
			
			ptr->prev->next=ptr->next;
			if (ptr->next!=NULL)
			ptr->next->prev=ptr->prev;
	
			if (tmp==NULL)
			{
				tmp=*q;
				ptr->prev=NULL;
				ptr->next=tmp;
				ptr->next->prev=ptr;
				*q=ptr;
			}
			else
			{
				tmp=tmp->next;
				tmp->prev->next=ptr;
				ptr->prev=tmp->prev;
				tmp->prev=ptr;
				ptr->next=tmp;
			}
		}


	}
}