Linked List Sorting/Swapping

This is a discussion on Linked List Sorting/Swapping within the C Programming forums, part of the General Programming Boards category; 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" ...

  1. #1
    Registered User
    Join Date
    Jan 2011
    Posts
    2

    Question 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
    Last edited by swinters; 02-23-2011 at 07:49 PM. Reason: code tags

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,159
    I don't think you're going to get anyone to help you until you USE CODE TAGS.
    If you understand what you're doing, you're not learning anything.

  3. #3
    Registered User
    Join Date
    Jan 2011
    Posts
    2
    Quote Originally Posted by itsme86 View Post
    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

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,337
    > 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?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,304
    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.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,262
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 08:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21