Thread: Sort Linked List Algorithm.

I've written a sort for a linked list (at least i thought i did), and can not figure out what is wrong. If I could get any help it would be appreciated.

html posted code
[edit]
below is excerpt from the source code. what i'm trying to do is call this public class member from another public class member that extracts the data from 2 other instansiated link list objects. the objects and the new sorted linked list are from the same class. i'm passing the object that I want the final list to be. basically i'm combining 2 already built lists and sorting them in the below function after i've extracted each individual node. it isn't working. i'm not getting any compile errors, but the logic must not be correct. when i run it it doesn't crash, but it doesn't fill the list with anything. I have been accused of not being percise enough, but i hope the details i'm providing cover the full aspect of my frustration. I know there are some genises that answer questions here so I beg you for your input.

Code:

 
void linklist::orderedlist(linklist *CopyC)
{  	//
	link *current , *previous;
	current = previous = head;

	link *newlink = new link;
	
	for(x=0;x<=SIZE;x++)
	{
		newlink->fname[x] = buffer1[x]; 
	}

	for(x=0;x<=SIZE;x++)
	{
		newlink->lname[x] = buffer2[x];
	}

	for(x=0;x<=SIZE;x++)
	{
		newlink->ssnumber[x] = buffer3[x];
	}

	newlink->age=age;
	newlink->weight=weight;

	newlink->next = NULL;

	if (head == NULL) //this tells me I have an empty list
	{
		head = newlink;
		tail = head;
	}
	else
	{
		//find the position to insert it
		while ( strcmp(current->lname,buffer2)==1 && current->next !=NULL)
		{
			previous = current;
			current = current->next;
		}

		if (current==head)//it will become the new head
		{
			newlink->next=head;
			head=newlink;
		}
		else
		{
			if (current->next==NULL)//becomes the new tail
			{
				tail->next=newlink;
				tail = newlink;
			}
			else
			{
				previous->next=newlink;
				newlink->next=current;
			}
		}
	}
}

i also tried this, but it doesn't work either.

Code:

 
void linklist::orderedlist(linklist *CopyC)
{  	//

	*CopyC->current = *CopyC->previous = *CopyC->head;

	*CopyC->link->node = new link;
	
	for(x=0;x<=SIZE;x++)
	{
		*CopyC->link->fname[x] = buffer1[x]; 
	}

	for(x=0;x<=SIZE;x++)
	{
		*CopyC->link->lname[x] = buffer2[x];
	}

	for(x=0;x<=SIZE;x++)
	{
		*CopyC->link->ssnumber[x] = buffer3[x];
	}

	*CopyC->link->age=age;
	*CopyC->link->weight=weight;

	*CopyC->link->next = NULL;

	if (*CopyC->head == NULL) //this tells me I have an empty list
	{
		*CopyC->head = *CopyC->link;
		*CopyC->tail = *CopyC->head;
	}
	else
	{
		//find the position to insert it
		while ( strcmp(*CopyC->current->lname,buffer2)==1 && *CopyC->current->next !=NULL)
		{
			*CopyC->previous = *CopyC->current;
			*CopyC->current = *CopyC->current->next;
		}

		if (*CopyC->current==*CopyC->head)//it will become the new head
		{
			*CopyC->link->next=*CopyC->head;
			*CopyC->head=*CopyC->link;
		}
		else
		{
			if (*CopyC->current->next==NULL)//becomes the new tail
			{
				*CopyC->tail->next=*CopyC->link;
				*CopyC->tail = *CopyC->link;
			}
			else
			{
				*CopyC->previous->next=*CopyC->link;
				*CopyC->link->next=*CopyC->current;
			}
		}
	}
}

[\edit]

source code .cpp file

If you want to copy a linked list, it should look something like this.

Code:

void linklist::copy(linklist *new_list)
{
   link *current;
   link *new_current;

   if (head == NULL)
      cout << "Empty list." << endl;
   {
      cout << "********** COPYING *********" << endl;
      current = head;
      while (current != NULL)
      {
         new_current = new link;
         new_current->next = NULL;
         if (new_list->head == NULL)
            new_list->head = new_current;
         else
            new_list->tail->next = new_current;
         new_list->tail = new_current;

         strcpy(new_current->fname, current->fname);
         strcpy(new_current->lname, current->lname);
         strcpy(new_current->ssnumber, current->ssnumber);
         new_current->age = current->age;
         new_current->weight = current->weight;
         current = current->next;
      }
   }
}

To sort a linked list, you have to decide:
1. What sort algorithm to use (bubble, quick, heap)
2. What item to sort by (name, ssnumber, etc)

Swoopy,

Thanks for the response... you always come through.
I'm looking to fix a sort that is ill.
As you can see I'm very confused.
below is my newest version that still doesn't work.
I have traced the code with node depictions and pointers over and over. It works in my head, but not in the program.
What the code is sapposed to do is merge two linked lists into a third ordered list. In the main i have two calls that pass two lists by reference. not at the same time, but one after the other. our teacher gave us this sort algorithm, but it doesn't work.
all it does is merge the two together without sorting.
i have ran numerous tests. i have determined that the data passes correctly. the buffers are filled. the strcmp() is spitting out correct test data, but it still will not sort. I believe my pointer combinations are off. but my trace works. i'm completely lost.
a follow up question is when do i get into the cool programming and not the confusing programming. hehehe i know that isn't a real question.

Code:

void linklist::orderedlist(linklist *list)
	{  
		initializeData();

		list->current=list->head;

		while (list->current != NULL)  
		{		
			for(x=0;x<=SIZE;x++)
			{
				buffer1[x]=list->current->fname[x]; 
			}

			for(x=0;x<=SIZE;x++)
			{
				buffer2[x]=list->current->lname[x];
			}

			for(x=0;x<=SIZE;x++)
			{
				buffer3[x]=list->current->ssnumber[x];
			}

			age=list->current->age;
			weight=list->current->weight;

			list->current = list->current->next;
			
			current = previous = head;

			link* newlink = new link;
		    
			for(x=0;x<=SIZE;x++)
			{
				newlink->fname[x] = buffer1[x]; 
			}

			for(x=0;x<=SIZE;x++)
			{
				newlink->lname[x] = buffer2[x];
			}

			for(x=0;x<=SIZE;x++)
			{
				newlink->ssnumber[x] = buffer3[x];
			}

			newlink->age=age;
			newlink->weight=weight;

			newlink->next = NULL;

			if (head == NULL) //this tells me I have an empty list
			{
				head = newlink;
				tail = head;
			}
			else
			{
				//find the position to insert it
				while ( strcmp(current->lname,buffer2)==1 && current->next !=NULL)
				{
					previous = current;
					current = current->next;
				}

				if (current==head)//it will become the new head
				{
					newlink->next=head;
					head=newlink;
				}
				else
				{
					if (current->next==NULL)//becomes the new tail
					{
						tail->next=newlink;
						tail = newlink;
					}
					else
					{
						previous->next=newlink;
						newlink->next=current;
					}
				}
			}
		}
	}

why can we not attach more than one file at a time?

i split it into 3 files for my teacher.
her is the last of the three

> //find the position to insert it
> while ( strcmp(current->lname,buffer2)==1 && current->next !=NULL)

I don't think it will help, but instead you might try:
//find the position to insert it
while ( strcmp(current->lname,buffer2)>0 && current->next !=NULL)

To sort a linked list, you have to decide:
1. What sort algorithm to use (bubble, quick, heap)
2. What item to sort by (name, ssnumber, etc)

Swoopy,

I believe what I recreated was a bubble sort with a linked list.
I'm sorry I didn't see this part of the post until just now.
I have rewritten this using strcpy(), but it hangs on the new revision. I accidently started a new thread due to I just found this one again.
new thread addresssing the same question.
check out the new thread for the revised code. I've been out of town and finally got back so I do appologize for this thread getting old.