Thread: 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.

> 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?

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.