Quicksort with LL

[azuk040891]

I'm trying to debug an implementation of Quicksort using a singly-linked list. I keep getting a seg fault right after running the program, which indicates that it lies somewhere early on in the sorting process. Any guesses?

I know, it's not ideal at all to use Quicksort as opposed to, say Mergesort. But this is for a class, and we have to implement quicksort using a singly-linked list.

Here is my QuickSort() function:

template <typename T>
void quicksort(SinglyLinkedList<T> & A, bool (* before)(T &, T &))
{
	SinglyLinkedList<T> Abefore, Aafter, pivot;
	typename SinglyLinkedList<T>::iterator pivotIt, Ait;

	if (A.size() > 1)
	{
		A.pop_front_push_other_front(pivot);
		pivotIt = pivot.begin();
		
		Ait = A.begin();
		do
		{
			if ((*before)(*Ait, *pivotIt))
				A.pop_front_push_other_front(Abefore);
			else A.pop_front_push_other_front(Aafter);

			Ait = A.begin();
		}
		while (Ait != A.end());

		if ((*before)(*Ait, *pivotIt))
			A.pop_front_push_other_front(Abefore);
		else A.pop_front_push_other_front(Aafter);

		quicksort(Abefore, before);
		quicksort(Aafter, before);
		A.append_clear_other(Abefore);
		A.append_clear_other(pivot);
		A.append_clear_other(Aafter);
	}
}

Here are the append_clear_other() and pop_front_push_other_front() member functions:

template <typename T>
void SinglyLinkedList<T>::pop_front_push_other_front(
    SinglyLinkedList<T> & y)
{
	int len = this->size();
	if (len >= 1)
	{
		Node * tmp = head->next;
		head->next = y.head;
		y.head = head;
		if (len == 1)
			head = tail = 0;
		else
			head = tmp;
	}
}


template <typename T>
void SinglyLinkedList<T>::append_clear_other(
    SinglyLinkedList<T> & y)
{
	if (empty())
		*this = y;
	else
	{
		tail->next = y.head;
		tail = y.tail;
		y.head = 0;
		y.tail = 0;
	}
}

You can assume several things. *operator has been overloaded for this class type's iterator object and returns the value pointed to by the iterator. (*before)() has been passed an appropriate before() function that returns true or false depending on the desired comparison.
the size() member function uses a for loop to count the current size of the list. And the =operator has been overloaded so that it assigns one list to another, and clears the other list.

[hamsterman]

Nothing stands out.. Though this is not a good method of debugging. Just litter your code with cout<<s until you know which line is the last one executed and what are the values of your variables at that point. That is, assuming that you can't use a debugger..