Segmentation Fault in singly linked list quicksort

[daman371]

I get a seg fault with this code.

int MyList::Partition(Node *temp, int start, int end)
{
	int pivotvalue,
	    pivotindex,
	    mid;

        Node * midptr,
		*stptr,
		*temp2,
		*endptr;

	stptr = temp;
	midptr = temp;

	mid = (start + end) /2;
	for (int index = 0; index < mid; index++)
		midptr = midptr->next;

	swap(stptr, midptr);
	pivotindex = start;
	pivotvalue = stptr->ID;
	temp2 = stptr->next;
	for (int scan = start + 1; scan <= end; scan++)
	{
		if (temp2->ID < pivotvalue)
		{
			pivotindex++;
			swap(stptr, temp2);
		}
		temp2 = temp2->next;
	}
	endptr = stptr;
	for (int index = 0; index < pivotindex; index++)
		endptr = endptr->next;
	swap(stptr, endptr);
	return pivotindex;
}

Do I need to check that ->next != NULL?

[helios]

Wouldn't it have been faster to test that yourself than make a post?
Yes, you probably should. It would help if you mentioned where it is that segmentation fault occurs.

[daman371]

I tried that and it didn't make a difference. Anyone have any ideas? The next thing I'm going to try is to rewrite the "scan" for loop. I don't think it will work, so, still any ideas will be appreciated.

[daman371]

Well changing the scan the way I said stops it from seg faulting, however, the sorted order is not correct. This is what I have. I'm still working on it but still any suggestions would be good.

int MyList::Partition(Node *temp, int start, int end)
{
	int pivotvalue,
	    pivotindex,
	    mid;

        Node * midptr,
		*stptr,
		*temp2,
		*endptr,
        *scan;

	stptr = temp;
	midptr = temp;

	mid = (start + end) /2;
	for (int index = 0; index < mid; index++)
	{
	    if (midptr->next != NULL)
		midptr = midptr->next;		
    }	

	swap(stptr, midptr);
	pivotindex = start;
	pivotvalue = stptr->ID;
	for (scan = stptr->next; scan != NULL; scan = scan->next)
	{
	    temp2 = stptr;
		if (temp2->ID < pivotvalue)
		{
			pivotindex++;
			for (int index = 0; index < pivotindex; index++)
			temp2 = temp2->next;
			swap(temp2, scan);
		}
	}
	endptr = stptr;
	for (int index = 0; index < pivotindex; index++)
	{
	    if (endptr->next != NULL)
		endptr = endptr->next;
    }	
	swap(stptr, endptr);
	return pivotindex;
}

[writetonsharma]

if you put your code in code tags you may get more replies..atleast one more!! :P

[daman371]

Sorry, I'm new here and didn't know code tags were supported. I made edits.

[daman371]

Well now I have this and this is supposed to work. I got it from my teacher and hers worked. Here is my code and below mine is hers.

int MyList::Partition(Node *temp, int start, int end)
{
	int pivotvalue,
	    pivotindex,
	    mid;

        Node * midptr,
		*stptr,
		*temp2,
		*endptr;

	stptr = temp;
	midptr = temp;
	endptr = temp;
	temp2 = temp;
	start = 0;
	
	mid = (start + end) / 2;
	for (int index = 0; index < mid-1; index++)
	{
	    if (midptr->next != NULL)
		midptr = midptr->next;		
    }	

	swap(stptr, midptr);
	pivotindex = start;
	pivotvalue = stptr->ID;
	for (int index = start + 1; index <= end; index++)
	{
	    for (int index2 = 0; index2 < index; index2++)
	    {
	        if (temp2->next != NULL)
            temp2 = temp2->next;
        }    
		if (temp2->ID < pivotvalue)
		{
			pivotindex++;
			for (int index3 = 0; index3 < pivotindex; index3++)
			{
			    if (endptr->next != NULL)
                endptr = endptr->next;
            }
			swap(stptr, temp2);
		}
	}
	swap(stptr, endptr);
	return pivotindex;
}

int MyList::Partition(int start, int end, int count)
{
int index,
mid,
num,
I,
J,
K;
salesman person,
temp;

Node * curptr,
         * ptr1,
         * ptr2;

end = count;
curptr = head;
ptr1 = head;
ptr2 = head;
start = 0;
mid = (start + end) / 2;
for (I = 0; I < mid-1; I++)
curptr = curptr->next;

temp = head->person;
head->person = curptr->person;
curptr->person = temp;

index = start;

num = head->person.number;
for (I = start + 1; I <= end; I++)
{
   for (J = 0; J < I; J++)
   ptr1 = ptr1->next;
   if (ptr1->person.number < num)
   {
        index++;
        for (K = 0; K < index; K++)
        ptr2 = ptr2->next;
        temp = head->person;
        head->person = ptr1->person;
        ptr1->person = temp;
    }
}
temp = head->person;
head->person = ptr2->person;
ptr2->person = temp;

return index;
}