Linked list bubble sort

This is a discussion on Linked list bubble sort within the C Programming forums, part of the General Programming Boards category; where do i start with a bubble sort on a linked list???...

  1. #1
    Unregistered
    Guest

    Question Linked list bubble sort

    where do i start with a bubble sort on a linked list???

  2. #2
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    from the linked list , the solution will depend on how you implement the linked list

  3. #3
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Post your list and I'll work on it later. After I hand out candies for the kids a.k.a Haloween

    Also specify by what key data you want the list sorted according to.

  4. #4
    Unregistered
    Guest
    struct empDetails {
    int empNumber;
    char empLastName[20];
    char empFirstName[20];
    float empRate;
    struct empDetails *next;
    };

    int main(int argc, char *argv[])
    {
    int field;
    struct empDetails *start, *temp, *tail;
    FILE *records;

    if (argc != 3) {
    printf("\nError - Incorrect number of arguements.");
    printf("\nSyntax: %s filename field.\n", argv[0]);
    exit(1);
    }
    field = atoi(argv[2]);
    if ((field < 1) || (field > 4)) {
    printf("\nError - Field must be an integer value in range 1 to 4\n");
    exit(1);
    }
    if ((records = fopen(recordFile, "r")) == NULL) {
    printf("\nError - Unable to access %s\n", recordFile);
    exit(1);
    }

    records = fopen(recordFile, "r"); /* Open file */

    temp = (struct empDetails *) malloc(sizeof(struct empDetails));
    fscanf(records, "%d%s%s%f", &temp->empNumber, temp->empLastName,
    temp->empFirstName, &temp->empRate);
    start = tail = temp;

    while (!feof(records)) { /* Allocate memory, read and store data */
    temp = (struct empDetails *) malloc(sizeof(struct empDetails));
    fscanf(records, "%d%s%s%f", &temp->empNumber, temp->empLastName,
    temp->empFirstName, &temp->empRate);
    if (start == NULL) {
    start = temp;
    tail = temp;
    }
    else {
    tail->next = temp;
    tail = temp;
    }
    }

    fclose(records);



    }


    sorting based on 3rd token from the command line
    if 1 then sort based on empNumber
    if 2 then sort based on empLastName
    if 3 then sort based on empFirstName
    if 4 then sort based on empRate

  5. #5
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Okay, I'll work on it as soon as I get up in the morning. Sounds cool. BTW I have done this before but not recently so I'll probably look some of this up. I would do it tonight but it's late already.

  6. #6
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Oh yeah, one more thing before I go to sleep. Lets put this thing in a function because it is useless without.

  7. #7
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Okay, I'm working on it. I remember doing this somehow where a pointer to the head of the list was passed to the function, and a 'new' list was returned. A new list was actually built, while the old list was deleted. Damn, where are those labs? I have a book here, I'll see what I can come up with. Give me a few hrs. I want to use functions and organize your code that you have already.

  8. #8
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Alright, I have found a way to sort a linked list. Does it have to be a bubble sort? The way I found to do it is that you pass a pointer to the list. You than disect that list while building a new ordered list. The new ordered lists gets returned. It's not exactly bubble sort although it is possible to use bubble sort. First though does it have to be? I think this other way is more efficient.

  9. #9
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Dude, are you there? I'll post my answer in about 1 hr. Tell me if you specifically need bubble sort.

  10. #10
    Registered User jasrajva's Avatar
    Join Date
    Oct 2001
    Posts
    99
    hi unregged

    why dont you try this

    get a fn t traverse until the end of list and hence return the no of nodes
    (u might do this in the first pass of the bubble sort as well)
    once you know the no of nodes you can bubble sort

    my textbook tells me that it would be like

    for 1 to n
    for 1 to n-1
    }
    }
    then as in bubble sort exchange the pointers instead of the data so its much faster

  11. #11
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Okay well I finished the program, but I have one question. What is the second arguement? Why don't you make that the data filepath as in:

    executablename datafilepath 1

    Because this would make the most sense, but for now here is the code without setting it up like that, but arg 2 is doesn't mean crap all for now, unless you want that to mean something. Let me know.

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    struct empDetails { 
    	int empNumber; 
    	char empLastName[20]; 
    	char empFirstName[20]; 
    	float empRate; 
    	struct empDetails *next; 
    }; 
    
    struct empDetails * BuildList(struct empDetails *);
    void PrintList(struct empDetails *);
    struct empDetails * SortList(struct empDetails *, int);
    int SortField(int argc , char *argv[] );
    
    ///////////////////////////////////////////////
    int main(int argc, char *argv[]) 
    { 
    	
    	struct empDetails  * list = NULL;
    	
    	int field = SortField(argc,argv);
    
    	list = BuildList(list);
    	PrintList(list);
    	printf("Above is the unsorted list.\n\n");
    
    	list = SortList(list, field);
    	PrintList(list);
    	printf("Above is the sorted list.\n\n");
    
    	return 0;
    
    } 
    ////////////////////////////////////////////////////////
    
    struct empDetails * BuildList(struct empDetails * hp)
    {
    	FILE *records; 
    
    	struct empDetails *newp = NULL;
    
    	if ((records = fopen("recordFile.txt", "r")) == NULL) { 
    		perror("\nError - No data file!"); 
    		exit(1); 
    	} 
    
    
    	newp = (struct empDetails *) malloc(sizeof(struct empDetails)); 
    	
    	while( fscanf(records, "%d%s%s%f", &newp->empNumber, newp->empLastName, 
    		newp->empFirstName, &newp->empRate) != EOF)
    	{
    		newp->next = NULL;
    
    		if(hp == NULL) 
    		{
    			hp = newp; 
    		}else
    		{
    			newp->next = hp;
    			hp = newp;
    		}
    		newp = (struct empDetails *) malloc(sizeof(struct empDetails)); 
    	} 
    	//delete allocated memory for the last node which is not needed
    	free(newp);
    
    	fclose(records); 
    	return hp;
    
    }
    ////////////////////////////////////////////////////////////////////////
    void PrintList(struct empDetails * hp)
    {
    	while(hp)
    	{
    		printf("%d %s %s %.2f is at memory address %p\n", hp->empNumber,
    			hp->empLastName, hp->empFirstName, hp->empRate, hp);
    		hp = hp->next;
    	}
    }
    //////////////////////////////////////////////////////////////////
    struct empDetails * SortList(struct empDetails * hp, int field)
    {
    	struct empDetails *freep = NULL, *returnp = NULL;
    	struct empDetails *prep = NULL, *curtp = NULL;
    	struct empDetails *newp = NULL;
    
    	while(hp)
    	{
    		//node for new list that will be returned
    		newp = (struct empDetails *) malloc (sizeof(struct empDetails));
    		newp->empNumber = hp->empNumber;
    		strcpy(newp->empLastName, hp->empLastName);
    		strcpy(newp->empFirstName, hp->empFirstName);
    		newp->empRate = hp->empRate;
    
    		newp->next = NULL;
    
    		//get rid of old list node by node
    		freep = hp;
    
    		//If this is the first node of the new list
    		if(returnp == NULL) 
    		{
    			returnp = newp;
    		}
    
    	
    		if(field == 1 && newp->empNumber > returnp->empNumber)
    			{
    				newp->next = returnp;
    				returnp = newp;
    			}
    			
    		if(field == 2 && strcmp(newp->empLastName,returnp->empLastName) > 0)
    			{
    				newp->next = returnp;
    				returnp = newp;
    			}
    	
    		if( field == 3 && strcmp(newp->empFirstName, returnp->empFirstName) > 0)
    			{
    				newp->next = returnp;
    				returnp = newp;
    			}
    
    		if(field == 4 && newp->empRate > returnp->empRate)
    			{
    				newp->next = returnp;
    				returnp = newp;
    			}
    
    		else
    		{
    			prep = returnp;
    			curtp = returnp->next;
    
    			if(field == 1) while(curtp != NULL && newp->empNumber < curtp->empNumber)
    
    			if(field == 2) while(curtp != NULL && strcmp(newp->empLastName,curtp->empLastName) < 0)
    
    			if(field == 3) while(curtp != NULL && strcmp(newp->empFirstName,curtp->empFirstName) < 0)
    	
    			if(field == 4) while(curtp != NULL && newp->empRate < curtp->empRate)
    			{
    				prep = curtp;
    				curtp = curtp->next;
    			}
    
    			prep->next = newp;
    			newp->next = curtp;
    		}//end of nested if else statments
    
    		//get next node of old list
    		hp = hp->next;
    		//free used node of old list
    		free(freep);
    	}//end of while
    
    	return returnp;
    }
    ////////////////////////////////////////////////////////
    int SortField(int argc , char *argv[] )
    {
    
    	/*
    	sorting based on 3rd token from the command line 
    	if 1 then sort based on empNumber 
    	if 2 then sort based on empLastName 
    	if 3 then sort based on empFirstName 
    	if 4 then sort based on empRate
    	*/
    
    	int field; 
    
    	if (argc != 3) { 
    		printf("\nError - Incorrect number of arguements."); 
    		printf("\nSyntax: %s filename field.\n", argv[0]); 
    		exit(1); 
    	} 
    
    	field = atoi(argv[2]); 
    
    	if ((field < 1) || (field > 4)) { 
    		printf("\nError - Field must be an integer value in range 1 to 4\n"); 
    		exit(1); 
    	} 
    	return field;
    
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  2. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 05:40 PM
  3. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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