Linked List Sorting/Swapping

Within my main I have to following code:

Code:

printf("SORTING OPTIONS:\n"
	"[1] Social Security Number\n"
	"[2] Character Code\n"
	"[3] Score\n"
	"[4] Year\n"
	"How do you wish to sort the list?>");
scanf("%c", &sort_option);
scanf("%c", &blank);
switch(sort_option){
	case '1':
	         sort_SSN(head);
	         break;
	case '2':
		sort_char_code(head);
		break;
	case '3':
		sort_score(head);
		break;
	case '4':
		sort_year(head);
		break;
}

curr=head;
while(curr != NULL){
	printf("%09d %15s %15s %6s %10d         ",
		curr->SSN, curr->f_name, curr->l_name, curr->char_code, curr->score );
	term(curr->year);
	curr = curr->next;
}

The functions that are called are all basically the same except for the sorting condition:

Code:

student_t *sort_SSN(student_t *head)
{
	student_t *ptr_a = head;
	student_t *ptr_b = ptr_a->next;
	int swap=1;
	while(swap != 0){
		swap=0;
		while(ptr_b != NULL){
			if(ptr_a->SSN < ptr_b->SSN){
				head = swap_student(ptr_a, ptr_b, head);
				ptr_a = ptr_a->next;
				ptr_b = ptr_b->next;
				swap=1;
			}else{
				ptr_a = ptr_a->next;
				ptr_b = ptr_b->next;
			}
		}
	}
	return(head);
}

student_t *sort_score(student_t *head)
{
	student_t *ptr_a = head;
	student_t *ptr_b = ptr_a->next;
	int swap=1;
	while(swap != 0){
		swap=0;
		while(ptr_b != NULL){
			if(ptr_a->score < ptr_b->score){
				head = swap_student(ptr_a, ptr_b, head);
				ptr_a = ptr_a->next;
				ptr_b = ptr_b->next;
				swap=1;
			}else{
				ptr_a = ptr_a->next;
				ptr_b = ptr_b->next;
			}
		}
	}
	return(head);
}

student_t *sort_year(student_t *head)
{
	student_t *ptr_a = head;
	student_t *ptr_b = ptr_a->next;
	int swap=1;
	while(swap != 0){
		swap=0;
		while(ptr_b != NULL){
			if(ptr_a->year < ptr_b->year){
				head = swap_student(ptr_a, ptr_b, head);
				ptr_a = ptr_a->next;
				ptr_b = ptr_b->next;
				swap=1;
			}else{
				ptr_a = ptr_a->next;
				ptr_b = ptr_b->next;
			}
		}
	}
	return(head);
}

student_t *sort_char_code(student_t *head)
{
	student_t *ptr_a = head;
	student_t *ptr_b = ptr_a->next;
	int swap=1;
	while(swap != 0){
		swap=0;
		while(ptr_b != NULL){
			if(strcmp(ptr_a->char_code, ptr_b->char_code) > 0){
				head = swap_student(ptr_a, ptr_b, head);
				ptr_a = ptr_a->next;
				ptr_b = ptr_b->next;
				swap=1;
			}else{
				ptr_a = ptr_a->next;
				ptr_b = ptr_b->next;
			}
		}
	}
	return(head);
}

And the swap function I call is:

Code:

student_t *swap_student(student_t *ptr_a, student_t *ptr_b, student_t *head)
{
	if(ptr_a->prev == NULL){
		ptr_b->next->prev = ptr_a;
		ptr_a->next = ptr_b->next;
		ptr_b->next = ptr_a;
		ptr_a->prev = ptr_b;
		ptr_b->prev = NULL;
		head = ptr_b;
	}else if(ptr_b->next == NULL){
		ptr_b->prev = ptr_a->prev;
		ptr_a->prev->next = ptr_b;
		ptr_a->prev = ptr_b;
		ptr_b->next = ptr_a;
		ptr_a->next = NULL;
	}else{
		ptr_a->next = ptr_b->next;
		ptr_b->next->prev = ptr_a;
		ptr_a->prev->next = ptr_b;
		ptr_b->prev = ptr_a->prev;
		ptr_a->prev = ptr_b;
		ptr_b->next = ptr_a;
	}
		return(head);
}

SO
there are a couple problems... first, my swap function works for structures in the middle of the list, but when I try to swap the first structure, it just somehow detatches the 2nd structure in the list and keeps the first as the head.

Secondly, my sort function wont run (I tested outside of the switch statement with the sort_SSN) and it just terminates the program in the middle of the first print statement. Is my mistake within my swap function? or my sort function?

Thanks

I don't think you're going to get anyone to help you until you USE CODE TAGS.

Originally Posted by itsme86

I don't think you're going to get anyone to help you until you USE CODE TAGS.

thanks itsme, i made that change. i appreciate the advice

> sort_SSN(head);
I see a lot of
return head;
statements in the functions, what's going to happen to the return result in main?

SO
there are a couple problems... first, my swap function works for structures in the middle of the list, but when I try to swap the first structure, it just somehow detatches the 2nd structure in the list and keeps the first as the head.

You only handle a being at the beginning and b being at the end. Will this be a problem, or will a always come before b when you call swap? You may need a few more if-else cases. Also note that a at the head and b at the tail shouldn't be mutually exclusive, so you might want to drop the else-if part. The easier way, IMO is to use a temp pointer, then do the "classic" swap. The following pseudo code should work no matter where a and b are. Just remember to return the new head if it changes.

Code:

set temp's prev & next to b's prev & next
set b's prev & next to a's prev & next
set a's prev & next to temp's prev & next

Secondly, my sort function wont run (I tested outside of the switch statement with the sort_SSN) and it just terminates the program in the middle of the first print statement. Is my mistake within my swap function? or my sort function?

I wouldn't worry about that until you fix your swap function. Make sure you have a working print_list function, and make a few simple tests to ensure your swap works (swapping all combinations of head, tail and middle elements) before moving on to sorting. You should code in small increments, and test as you go.

Both.

1. You've not realised that upon return from your swap function that ptr_a follows ptr_b rather than ptr_b following ptr_a. Thus the rest of your traversal is screwed up.

2. Your swap_student function doesn't work correctly when there are exactly two items in the list, i.e. when ptr_a->prev == NULL and ptr_b->next == NULL

On a final note, although bubble sort is very easy for arrays, implementing it for linked lists is actually pretty difficult. It turns out that insertion sort is the easiest to implement for linked-lists, and is even a tiny bit more efficient.

Duplicating the sorting algorithm code is not what people do in the real world when they might want to sort by various different criteria, but I'm not going to go into describing how to use a switch statement or function pointers for it at this time. It would be good for you to look into those options when you can.