teddybouch 0 Newbie Poster

I am trying to sort a linked list, and not being terribly familiar with sorting algorithms, I just found a merge sort on Wikipedia and decided to go with it. Hence, I apologize if I'm missing something obvious. Based on the printout statements that I inserted into the code, it looks like my problem has to do with returning the linked list - everything proceeds normally until I need to make the first return, and then it just crashes.

Here's the sorting code. It is completely based on the example pseudocode shown as an example in the Wikipedia article, with changes made to syntax to fit my application.

static list mergeSortX( list sortMe )
{
	// Declare variables
	list left, right, result;
	int middle;
	double contents[2];
	double temp[2];

	printf("In mergeSortX with length %d\n", sortMe.count());

	// Return if the length is one or less
	if ( sortMe.count() <= 1 )
	{
		printf("returning = ");
		for ( int i = 0; i < sortMe.count(); i++ )
		{
			sortMe.access( i, temp );
			printf( "(%f, %f), ", temp[0], temp[1] );
		}
		printf("\n");

		printf("Sorted by length, returning...\n");
		return sortMe;
	}

	// Find the middle index of the list
	middle = sortMe.count() / 2;
	printf("middle = %d\n", middle);

	// Take elements 0 to middle and put them in left
	for( int i = 0; i < middle; i++ )
	{
		sortMe.access( i, contents );
		left.append( contents[0], contents[1] );
	}

	printf("left = ");
	for ( int i = 0; i < left.count(); i++ )
	{
		left.access( i, temp );
		printf( "(%f, %f), ", temp[0], temp[1] );
	}
	printf("\n");


	// Take elements middle to end and put them in right
	for( int j = middle; j < sortMe.count(); j++ )
	{
		sortMe.access( j, contents );
		right.append( contents[0], contents[1] );
	}

	printf("right = ");
	for ( int i = 0; i < right.count(); i++ )
	{
		right.access( i, temp );
		printf( "(%f, %f), ", temp[0], temp[1] );
	}
	printf("\n");


	// Sort the left and right lists recursively
	left = mergeSortX( left );
	printf("Sorted left = ");
	for ( int i = 0; i < left.count(); i++ )
	{
		left.access( i, temp );
		printf( "(%f, %f), ", temp[0], temp[1] );
	}
	printf("\n");
	right = mergeSortX( right );

	// Merge the result into one list
	printf("Merging lists...\n");
	result = mergeX( left, right );

	printf("result = ");
	for ( int i = 0; i < result.count(); i++ )
	{
		result.access( i, temp );
		printf( "(%f, %f), ", temp[0], temp[1] );
	}
	printf("\n");

	printf("Leaving mergeSortX\n");

	return result;
}

static list mergeX( list left, list right )
{
	// Declare variables
	list result;
	double firstLeft[2];
	double firstRight[2];

	// Merge the lists, maintaining order
	while ( ( left.count() > 0 ) and ( right.count() > 0 ) )
	{
		left.access( 0, firstLeft );
		right.access( 0, firstRight );
        	if ( firstLeft[0] <= firstRight[0] )
		{
			// Append the first element of left to the result and remove from left
			result.append( firstLeft[0], firstLeft[1] );
            		left.del( firstLeft[0], firstLeft[1] );
		}
        	else
        	{
			// Append the first element of right to the result and remove from right
			result.append( firstLeft[0], firstLeft[1] );
            		right.del( firstLeft[0], firstLeft[1] );
		}
	}

    	while ( left.count() > 0 ) 
	{
		left.access( 0, firstLeft );
		result.append( firstRight[0], firstRight[1] );
        	left.del( firstRight[0], firstRight[1] );
	}

    	while ( right.count() > 0 ) 
	{
		right.access( 0, firstRight );
		result.append( firstRight[0], firstRight[1] );
        	right.del( firstRight[0], firstRight[1] );
	}

    	return result;

}

The next thing I wanted to include was my linked list class, in case the problem lies there.

class list
{
     private:

         struct node
         {
            double xData;
			double yData;
            node *link;
         }*p;

   public:

         list();
         void append( double x, double y );
         void del( double x, double y );
		 void access( int index, double contents[] );
         int count();
         ~list();
};

list::list()
{
     p=NULL;
}

void list::append( double x, double y )
{
   node *q,*t;

   if( p == NULL )
   {
      p = new node;
      p->xData = x;
	  p->yData = y;
      p->link = NULL;
   }
   else
   {
      q = p;
      while( q->link != NULL )
	  {
		  q = q->link;
	  }

      t = new node;
      t->xData = x;
	  t->yData = y;
      t->link = NULL;
      q->link = t;
   }
}

void list::del( double x, double y )
{
   node *q,*r;
   q = p;

   if(( q->xData == x ) && ( q->yData == y ))
   {
      p = q->link;
      delete q;
      return;
   }

   r = q;
   while( q!=NULL )
   {
      if(( q->xData == x ) && ( q->yData == y ))
      {
         r->link = q->link;
         delete q;
         return;
      }

      r = q;
      q = q->link;
   }
   printf("Element (%f, %f) not Found.\n", x, y);
}

void list::access( int index, double contents[])
{
	node *q;
    int c=0;
    for( q=p ; c<index ; c++ )
	{
        q = q->link;
	}

	contents[0] = q->xData;
	contents[1] = q->yData;
}

int list::count()
{
   node *q;
   int c=0;
   for( q=p ; q != NULL ; q = q->link )
        c++;

   return c;
}

list::~list()
{
   node *q;
   if( p == NULL )
        return;

   while( p != NULL )
   {
        q = p->link;
      delete p;
      p = q;
   }
}

Finally, here's some test output that I have in case it will shed some light on what is going on:

doX = 1
List before = (-5.617623, -2.034482), (-5.506881, -2.153052), (-5.377584, -2.276156), (-5.249851, -2.403839), (-5.120810, -2.536295), (-4.969870, -2.675439), (-4.833482, -2.818779), (-5.732594, -1.919852), (-5.851091, -1.809288), (-5.956030, -1.701978), (-6.108007, -1.492484), 
In mergeSortX with length 11
middle = 5
left = (-5.617623, -2.034482), (-5.506881, -2.153052), (-5.377584, -2.276156), (-5.249851, -2.403839), (-5.120810, -2.536295), 
right = (-4.969870, -2.675439), (-4.833482, -2.818779), (-5.732594, -1.919852), (-5.851091, -1.809288), (-5.956030, -1.701978), (-6.108007, -1.492484), 
In mergeSortX with length 5
middle = 2
left = (-5.617623, -2.034482), (-5.506881, -2.153052), 
right = (-5.377584, -2.276156), (-5.249851, -2.403839), (-5.120810, -2.536295), 
In mergeSortX with length 2
middle = 1
left = (-5.617623, -2.034482), 
right = (-5.506881, -2.153052), 
In mergeSortX with length 1
returning = (-5.617623, -2.034482), 
Sorted by length, returning...

Thanks very much for the help!