Thread: Linked list bubble sort

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

from the linked list , the solution will depend on how you implement the linked list

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.

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

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.

Oh yeah, one more thing before I go to sleep. Lets put this thing in a function because it is useless without.

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.

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.

Dude, are you there? I'll post my answer in about 1 hr. Tell me if you specifically need bubble sort.

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;

}