Thread: Sorting Linked List Problem

  1. #1
    Registered User chriscolden's Avatar
    Join Date
    Jan 2006
    Posts
    32

    Sorting Linked List Problem (Bubble... I Know)

    Hi all.

    Hopefully a simple answer but I just can't see it.

    I am trying to perform a simple exchange sort on a linked list.

    I have had the code working with a normal array but cannot seem to get the swapping of two records correct.

    I'm getting a General Protection Error and the program terminates.

    my code for swapping the records is

    Code:
    // If elap is negitive then it must be moved.
    			if ( elap < 0 ) {
    				tempRecord->next = ptrNew2->next;
    				ptrNew2->next = prevNode->next;
    				prevNode->next = ptrNew->next;
    				ptrNew->next = tempRecord->next;
    			}
    tempRecord is a temperay store while the swap takes place,
    prevNode is the record before the two that need to swap
    ptrNew and ptrNew2 are the record that need swapping

    Thanks alot for your help. I'm probably being really dense.

    Chris

    ps. Id prefer to keep it as an exchange sort as i'm new too C. I am aware there are better sorting methods.
    Last edited by chriscolden; 01-16-2006 at 06:54 PM.

  2. #2
    Registered User chriscolden's Avatar
    Join Date
    Jan 2006
    Posts
    32
    sorry my bad

    this is working correctly. my problem was because i forgot to re-terminate terminate the list after creating a new record.

    I'm sorry if i have wasted anyones time.

    Chris

  3. #3
    ~viaxd() viaxd's Avatar
    Join Date
    Aug 2003
    Posts
    246
    you also can write it without temp, like this:
    Code:
    new->next = new2->next;
    new2->next = new;
    prev->next = new2;
    :wq

  4. #4
    Registered User chriscolden's Avatar
    Join Date
    Jan 2006
    Posts
    32
    ok new problem.

    i have the following code to perform an exchange sort

    Code:
    void sortRecords(RECORD * ptrDatabase, int * counter) {
    	// Setup variables used within function
    	char temp[5];
    	RECORD * ptrNew, * ptrNew2, * prevNode, * tempRecord;
    	int dd1, mm1, yy1, dd2, mm2, yy2;
    	long elap;
    	
    	ptrNew = ptrDatabase;	// Make ptrNew = ptrDatabase so ptrDatabase is not modified.
    	
    	// Run through all records - 1
    	while (ptrNew->next!=(RECORD*) NULL){
    		prevNode = ptrNew;
    		ptrNew = ptrNew->next; /* first item doesn't contain data, last does */
    		
    		if(ptrNew->next == NULL) break;
    
    		// Get the dateAdded string and turn it into integers for processing
    		temp[0] = ptrNew->data.dateAdded[0];
    		temp[1] = ptrNew->data.dateAdded[1];
    		temp[2] = '\0';
    		dd1 = atoi(temp);
    
    		temp[0] = ptrNew->data.dateAdded[3];
    		temp[1] = ptrNew->data.dateAdded[4];
    		temp[2] = '\0';
    		mm1 = atoi(temp);
    
    		temp[0] = ptrNew->data.dateAdded[6];
    		temp[1] = ptrNew->data.dateAdded[7];
    		temp[2] = ptrNew->data.dateAdded[8];
    		temp[3] = ptrNew->data.dateAdded[9];
    		temp[4] = '\0';
    		yy1 = atoi(temp);
    		
    		ptrNew2 = ptrNew->next;
    
    		// Run through all records after the current pass number
    		while (ptrNew2->next!=(RECORD*) NULL){
    			// Get the dateAdded string and turn it into integers for processing
    			temp[0] = ptrNew2->data.dateAdded[0];
    			temp[1] = ptrNew2->data.dateAdded[1];
    			temp[2] = '\0';
    			dd2 = atoi(temp);
    
    			temp[0] = ptrNew2->data.dateAdded[3];
    			temp[1] = ptrNew2->data.dateAdded[4];
    			temp[2] = '\0';
    			mm2 = atoi(temp);
    
    			temp[0] = ptrNew2->data.dateAdded[6];
    			temp[1] = ptrNew2->data.dateAdded[7];
    			temp[2] = ptrNew2->data.dateAdded[8];
    			temp[3] = ptrNew2->data.dateAdded[9];
    			temp[4] = '\0';
    			yy2 = atoi(temp);
    
    			elap = days(dd1, mm1, yy1, dd2, mm2, yy2);	// Work out how many days have passed between the two dates
    
    			// If elap is negitive then it must be moved.
    			if ( elap < 0 ) {
    				tempRecord->next = ptrNew->next;
    				ptrNew->next = ptrNew2->next;
    				ptrNew2->next = tempRecord->next;
    				prevNode->next = ptrNew2;
    				
    				ptrNew2 = ptrNew->next;
    				ptrNew = prevNode->next;
    				//ptrNew = prevNode->next;
    				//ptrNew2 = 
    				
    
    				/*ptrNew->next = ptrNew2->next;
    				ptrNew2->next = ptrNew;
    				prevNode->next = ptrNew2;*/
    			}
                            else {
    				ptrNew2 = ptrNew2->next; /* first item doesn't contain data, last does */
    			}
    		}
    	}
    }
    However it does not sort the data propperly. I am guess its because when I do a swap of the records i am messing up when I acutually am with the sort on a whole. eg. ptrNew is much further down the list than it should be. its kinda hard to explain. If you have a look at the code though I think you should be able to see what i mean.

    Thanks for your help

    Chris

  5. #5
    Registered User chriscolden's Avatar
    Join Date
    Jan 2006
    Posts
    32
    UPDATE:

    I have changed modifing the pointers to simply moving the data between the two. This however had no effect. So i'm now more inclinded to say its the while loops its self.

    I have adapted the while loops from for loops.....

    Code:
    /* Exchange sort */
    
    void sort(void)
    {
            int temp,passno,i;
            for ( passno = 0 ; passno < n - 1 ; passno++)
                    for ( i = passno+1 ; i < n ; i++ )
                    if ( a[i] < a[passno] )
                    {
                            temp = a[i];
                            a[i] = a[passno];
                            a[passno] = temp;
                    }
    }
    
    /*----------------------------------------------------------------------------------------*/
    
            45      84      12      9       34      1       62      87      3       51
            1       84      45      12      34      9       62      87      3       51
            1       3       84      45      34      12      62      87      9       51
            1       3       9       84      45      34      62      87      12      51
            1       3       9       12      84      45      62      87      34      51
            1       3       9       12      34      84      62      87      45      51
            1       3       9       12      34      45      84      87      62      51
            1       3       9       12      34      45      51      87      84      62
            1       3       9       12      34      45      51      62      87      84
            1       3       9       12      34      45      51      62      84      87
    
    /*--------------------------------------------------------------------------------------*/
    However I am not sure if there is a problem with them or if there is what the problem is.

    If someone could point me in the right direction that would be great.

    Cheers

    Chris

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    A problem you need to address is when you swap the head of the list, you need to return a modified head pointer back to the caller.

    Personally, I'd add a "sortedInsert" function to your list functions, so that you can preserve the sort order of the list as you add new nodes (rather than simply adding to the tail for example).

  7. #7
    Registered User chriscolden's Avatar
    Join Date
    Jan 2006
    Posts
    32
    Ok i see what your saying but I should never have to modify the head of the list as there is a dummy record sitting at the start. which is why when I first go into the first while loop I move it on to the next record. ie what the dummy record ->next is pointing to.

    Am I completely off track here??

    I know its not good programming to leave records in the list that are never used but its the way we have been told to do it. Its an aim to make the introduction to link lists easier.

    Thanks again for your help. Its much apreciated.

    Chris

    ps. sorry for all the questioning. Just trying to get my head around it.
    I'm a noob when it comes to C and I have to use Borland C++ 3.1 because my university won't move on.

    However I do use Turbo C++ 3.1 for windows. Makes life abit less stressful.

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    It might be clearer if you separated out some functionality.
    Like

    // return -1 if a is before b, +1 if a is after b, or 0 if equal
    int compareNodes ( RECORD *a, RECORD *b );

    // prev_a->next and prev_b->next are swapped
    void swapNodes ( RECORD *prev_a, RECORD *prev_b );

    Or however you want to break that large function up into something more manageable.

  9. #9
    Registered User chriscolden's Avatar
    Join Date
    Jan 2006
    Posts
    32
    Hi thanks for all your help. I decided to go for an Insertion Sort. It was easier to code and will give me better results.

    Cheers
    I'm a noob when it comes to C and I have to use Borland C++ 3.1 because my university won't move on.

    However I do use Turbo C++ 3.1 for windows. Makes life abit less stressful.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  2. I need help on this particular Linked List problem
    By sangken in forum C Programming
    Replies: 11
    Last Post: 08-06-2006, 12:26 AM
  3. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM