help with sorting a list :(

I'm stuck on this problem. I've been trying for days figuring out how to fix it. I have a linklist.. I want to sort it alphabetically, i'm almost there but the functionnn has a few bugs:

The output for the following code:

Androd
Dog
Bat

as you can see... the last element comes before alphabetically before the previous one my sort method does not handle it. Does anyone know how to fix this? (the code in bold indicates where the problem is)

Code:

#include <stdio.h> #include <stdlib.h> #include <string.h> struct charNode { char petName[12]; struct charNode *next; }; typedef struct charNode charNode; void addElement(charNode **start, char *petName); void printList(charNode *start); charNode* newNode(char *petName); void getString(charNode *start); charNode *sort(charNode *start); charNode *reverse(charNode *head); int main() { charNode *start = NULL; getString(start); return 0; } void getString(charNode *start) { addElement(&start, "Dog"); addElement(&start, "Androd"); addElement(&start, "Bat"); start = sort(start); printf("\n"); printf("\n"); printList(start); } void addElement(charNode **start, char *petName) { charNode *temp,*prev, *loc; int i; temp = newNode(petName); if (*start == NULL) { *start = temp; } else { loc = *start; prev = NULL; for (i=0; loc != NULL; i++) { prev = loc; loc = loc->next; } if (prev == NULL) { *start = temp; } else { prev->next = temp; } } } charNode* newNode(char *petName) { charNode *temp; temp = (charNode *) malloc(sizeof(charNode)); if (temp == NULL) { printf("WARNING - Memory allocation error\n"); exit(EXIT_FAILURE); } strcpy(temp->petName, petName); temp->next = NULL; return temp; } void printList(charNode *start) { while (start != NULL) { printf("%s\n", start->petName); start = start->next; } } charNode *sort(charNode *start) { charNode *temp = NULL; charNode *prev = NULL; charNode *current = start; if (start!=NULL) { if (start->next != NULL) { prev = start; current = start; while (current != NULL) { if ( strcmp(current->petName, start->petName) <0) { prev->next = current->next; temp = start; start = current; start->next = temp; } else prev = current; current = current->next; } } } return start; }

Code:

if (start->next != NULL) { prev = start; current = start; // assigning current to start while (current != NULL) // so current == start rite? { if ( strcmp(current->petName, start->petName) <0) // checking the same thing? no?

and another hint :
strcmp returns 0 , < 0 and > 0 if the strings are same, less than or greater than respectively

yes in the first iteration the first element is compared to it self but as the loop progresses this isnt the case.

your code is pretty inefficient and unneccesarily long... but anw, the problem you are having was that you sort the list once only

so if you have something like

Code:

"z" -> "d" -> "x" -> "c" -> NULL

it will get to

Code:

"d" -> "x" -> "c" -> "z" -> NULL

and your sort will quit

and your strcmp check is still insufficient :)

try this

Code:

#include <string.h> #include <stdio.h> int main() { printf("%d\n", strcmp("aab", "aac")); printf("%d\n", strcmp("aab", "aaa")); return 0; }

It appears to me as though you're always swapping start when you'd really want to be swapping prev. Even at that, though your loop is missing comparisons. If I were you, I'd make another function, swap(a,b), that swaps 2 elements of your linked-list, that way in your sort you won't have to worry too much about all that pointer logic.

Quote:

Originally Posted by yxunomei

your code is pretty inefficient and unneccesarily long... but anw, the problem you are having was that you sort the list once only

so if you have something like

Code:

"z" -> "d" -> "x" -> "c" -> NULL

it will get to

Code:

"d" -> "x" -> "c" -> "z" -> NULL

and your sort will quit

yes exactly.... but if i run the same sort again and it doesn't change it. For example after "swap" runs we get:

Androd
Dog
Bat

if we run swap again

we get:

Code:

if ( strcmp(current->petName, start->petName) <0)

Androd < Androd == false

Code:

if ( strcmp(current->petName, start->petName) <0)

Dog < Androd == false

Code:

if ( strcmp(current->petName, start->petName) <0)

Bat < Androd == false

...so nothing changes :| any ideas on how to make it more efficient ?

what was your original input?

Quote:

Originally Posted by Happy_Reaper

It appears to me as though you're always swapping start when you'd really want to be swapping prev. Even at that, though your loop is missing comparisons. If I were you, I'd make another function, swap(a,b), that swaps 2 elements of your linked-list, that way in your sort you won't have to worry too much about all that pointer logic.

Actually i've thought about (comparing prev with current and swap) this but then that still wouldn't work cause it won't for certain sort the list:

unsorted list:

A C D Z B

ACDBZ

so it isn't really sorted :/

yes, but that's because you're updating things too quickly and missing comparisons. You should only update prev to prev-> next in what I'm showing you. Then, when if prev == current, then reset prev to start and current to current-> next. That should cover all the comparisons, in which case, as long as you're swapping right, will sort your list.

Quote:

Originally Posted by Happy_Reaper

yes, but that's because you're updating things too quickly and missing comparisons. You should only update prev to prev-> next in what I'm showing you. Then, when if prev == current, then reset prev to start and current to current-> next. That should cover all the comparisons, in which case, as long as you're swapping right, will sort your list.

ok i've did what you suggested (i.e. swap prev rather than start ) but i get an endless loop :|

Code:

charNode *sort(charNode *start) { charNode *temp = NULL; charNode *prev = NULL; charNode *current = start; if (start!=NULL) { if (start->next != NULL) { prev = start; current = start; while (current != NULL) { if ( strcmp(current->petName, prev->petName) <0) { prev->next = current->next; temp = prev; prev = current; start->next = temp; } else prev = current; current = current->next; } } } return start; }

Quote:

what was your original input?

Dog
Androd
Bat

If i can get the above to work i guess the solution for sorting and the guarantee that it will be sorted will be to run the sort method X number of times the linked list size is so if the linked list is 5 if i run the sort method 5 times and it swaps each adjacent element (if its out of place) then it should work...

Code:

"z" -> "x" -> "y" -> "d" -> "e" -> NULL ^ ^ prev next // compare and swap when required (1) "x" -> "z" -> "y" ... -> NULL ^ ^ prev next // same as above (2) etc

5 times yes...
and on this part

Code:

while (current != NULL) { if ( strcmp(current->petName, prev->petName) <0) { prev->next = current->next; temp = prev; prev = current; start->next = temp; } else prev = current; current = current->next; }

you see, if the strings are different, it will be swapped accordingly, and on the next iteration, current will be the same as prev rite? therefore on the next iteration, you will be comparing yet the same thing again... so according to you, you will need 2 * linked list size = 10 in your case rite?

that's inefficient? :D

Quote:

yes exactly.... but if i run the same sort again and it doesn't change it. For example after "swap" runs we get:

Androd
Dog
Bat

well, if that doesn't work, then tell me how you can make

Quote:

Dog
Androd
Bat

to

Quote:

Androd
Dog
Bat

Quote:

Originally Posted by yxunomei

Code:

"z" -> "x" -> "y" -> "d" -> "e" -> NULL ^ ^ prev next // compare and swap when required (1) "x" -> "z" -> "y" ... -> NULL ^ ^ prev next // same as above (2) etc

Quote:

iteration, current will be the same as prev rite? therefore on the next iteration, you will be comparing yet the same thing again...

i have tried adding:

Code:

current = current->next;

after this line:

Code:

prev = current;

but the endless loop is still there ? :( whats the problem

im getting confused by ur code ... T_T ...

tell me how you want those to be working and also what's actually happening in your code

i'll give you a bit of help with codes

Code:

charNode *sort(charNode *start) { charNode *temp = NULL; charNode *prev = NULL; charNode *current = NULL; charNode *currentIn = NULL; // if the list was empty or has only one item on it, we bother not doing anything if(start == NULL || start->next == NULL) { return start; } prev = start; // to keep track on the item before current // use for loop, easier to understand in this case for( current = start->next; current != NULL; current = current->next ) { // we need the nested loop to swap the list multiple times (in this case 5 times) for( currentIn = start->next; currentIn != NULL; current = currentIn->next) { // do the swapping here; } }

Ok we have the following items in the list:

Dog
Androd
Bat

this is only for the first iteration...

Code:

while (current != NULL) // keep looping till the end.... { if ( strcmp(current->petName, prev->petName) <0) /* IF Androd is smaller than Dog == TRUE */ { prev->next = current->next; /* this is just saying Androd = Androd */ temp = prev; /* place "prev" i.e. Dog in a temporary variable */ prev = current; /* place current (Androd) to prev (Dog) so we have Androd, Dog } else prev = current; // keep track of the previous item current = current->next; // move current after prev }

edit: actually the result is the following:

Dog
Bat

dunno what the hell went wrong :|

:D that sounds rite to me :p ... you are copying the address of the pointer, not the actual string :)

try this

Code:

while (current != NULL) {// keep looping till the end.... printf("%p %p %p %p\n, prev, current, temp, start); // <--- add this if ( strcmp(current->petName, prev->petName) <0) /* IF Androd is smaller than Dog == TRUE */ { prev->next = current->next; /* this is just saying Androd = Androd */ temp = prev; /* place "prev" i.e. Dog in a temporary variable */ prev = current; /* place current (Androd) to prev (Dog) so we have Androd, Dog // um, you are not using the temp? } else prev = current; // keep track of the previous item current = current->next; // move current after prev }

and tell me what's get printed

Ok, before you can sort, you're going to have to be able to swap the elements of your list correctly. And as of now, you're just not doing that.

To swap two elements, you need to swap their next pointers, you seem to be doing that much. BUT, you must ALSO swap the next pointers of their respective successors. If you don't do that, you'll end up with loads aof garbage any time you switch things around. Now I'm not sure if that's the exact cause of your infinite loop, but it wouldn't surprise me.

Anyhow, first getting swapping to work right. Then think about sorting.

is there an example somewhere? with just a simple * swap* ?

i have tried following... but the list remains unsorted :|

http://www.experts-exchange.com/Prog..._20914849.html

Code:

charNode *sort(charNode *start) { charNode *ptr1, *ptr2 = start; while (ptr1 != NULL) { ptr2 = ptr1; while (ptr2 != NULL) { if ( strcmp(ptr1->petName, ptr2->petName) <0) { ptr2 = ptr2->next; } } ptr1 = ptr1->next; } return start; }

also...re: to your q

003D2C90 003D2C60 00000000 003D2C60
003D2C60 003D2C78 00000000 003D2C60
003D2C78 003D2C90 003D2C60 003D2C60

simple int swap

Code:

#include <stdio.h> void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } int main() { int a = 3 , b = 5; swap(&a, &b); printf("%d %d\n", a, b); }

thanks but swapping ints in its self is easy (basically you're just passing the addresses to swap deref that address and get its value, assigning it to temp and swapping the values around). But in a list its much more difficult..:/

Code:

while (current != NULL) { if ( strcmp(current->petName, prev->petName) <0) { prev->next = current->next; temp = prev; prev = current; } else prev = current; current = current->next; }

Code:

previous current temp start 003D2C90 003D2C60 00000000 003D2C60 // zwha??? :O ... I thought previous == current?? 003D2C60 003D2C78 00000000 003D2C60 003D2C78 003D2C90 003D2C60 003D2C60

this is sort of unexpected ?? can you post your newest code with this?

as to your code up there, I wouldn't wonder... there's no swapping at all... it just basically go thru the list

i have modified your swap method:

Code:

void swap(charNode **a, charNode **b) { charNode *temp; temp = *a; *a = *b; *b = temp; }

by running: swap(&start, &start->next);

the problem is it prints

Androd
Bat

no last node?? :(

original list:

addElement(&start, "Dog");
addElement(&start, "Androd");
addElement(&start, "Bat");

Quote:

Originally Posted by yxunomei

this is sort of unexpected ?? can you post your newest code with this?

as to your code up there, I wouldn't wonder... there's no swapping at all... it just basically go thru the list

Code:

charNode *sort(charNode *start) { charNode *prev, *temp = NULL; charNode *current = start; while (current != NULL) {// keep looping till the end.... printf("%p %p %p %p\n", prev, current, temp, start); // if ( strcmp(current->petName, prev->petName) <0) { prev->next = current->next; *temp = *prev; *prev = *current; } else prev = current; // keep track of the previous item current = current->next; // move current after prev } return start; }

T_T_T_T_T_T ....

OK... I need you to do the following...

1. compile your newest code with the print thing I gave you earlier...
2. copy paste the exact result

start = sort(start);

ok:

Code:

charNode *sort(charNode *start) { charNode *prev, *temp = NULL; charNode *current = start; while (current != NULL) { printf("%p %p %p %p\n", prev, current, temp, start); if ( strcmp(current->petName, prev->petName) <0) { prev->next = current->next; temp = prev; prev = current; } else prev = current; current = current->next; } return start; }

result:

003D2C90 003D2C60 00000000 003D2C60
003D2C60 003D2C78 00000000 003D2C60
003D2C78 003D2C90 003D2C60 003D2C60

Dog
Bat

and this is the complete code for the swap function earlier (i can't get it to work properly...the end node is missing??)

Code:

#include <stdio.h> #include <stdlib.h> #include <string.h> struct charNode { char petName[12]; struct charNode *next; }; typedef struct charNode charNode; void addElement(charNode **start, char *petName); void printList(charNode *start); charNode* newNode(char *petName); void getString(charNode *start); void swap(charNode **a, charNode **b); int main() { charNode *start = NULL; getString(start); return 0; } void getString(charNode *start) { addElement(&start, "Dog"); addElement(&start, "Androd"); addElement(&start, "Bat"); swap(&start, &start->next); printList(start); } void addElement(charNode **start, char *petName) { charNode *temp,*prev, *loc; int i; temp = newNode(petName); if (*start == NULL) { *start = temp; } else { loc = *start; prev = NULL; for (i=0; loc != NULL; i++) { prev = loc; loc = loc->next; } if (prev == NULL) { *start = temp; } else { prev->next = temp; } } } charNode* newNode(char *petName) { charNode *temp; temp = (charNode *) malloc(sizeof(charNode)); if (temp == NULL) { printf("WARNING - Memory allocation error\n"); exit(EXIT_FAILURE); } strcpy(temp->petName, petName); temp->next = NULL; return temp; } void printList(charNode *start) { while (start != NULL) { printf("%s\n", start->petName); start = start->next; } } void swap(charNode **a, charNode **b) { charNode *temp; temp = *a; *a = *b; *b = temp; }

any idaes?

your prev isn't initialized

Code:

charNode *prev, *temp = NULL;

try this

Code:

charNode *sort(charNode *start) { charNode *prev = NULL, *temp = NULL; charNode *current = NULL; if(start == NULL || start->next == NULL) { // have you tried this?? return start; } current = start->next; prev = current; while (current != NULL) { printf("%p %p %p %p\n", prev, current, temp, start); if ( strcmp(current->petName, prev->petName) < 0) { swap(current, prev); // I'm not sure about this, try it } prev = current; current = current->next; } return start; }

compile, run, copy paste the exact stuff

noooooooo :(

00000000 003D2C78 00000000 003D2C60

and then crashes

i had to change:

swap(current->petName, prev->petName); // I'm not sure about this, try it

to

swap(&current, &prev); // I'm not sure about this, try it

otherwise it wouldn't compile...

Code:

#include <stdio.h> #include <stdlib.h> #include <string.h> struct charNode { char petName[12]; struct charNode *next; }; typedef struct charNode charNode; void addElement(charNode **start, char *petName); void printList(charNode *start); charNode* newNode(char *petName); void getString(charNode *start); void swap(charNode **a, charNode **b); charNode *sort(charNode *start); int main() { charNode *start = NULL; getString(start); return 0; } void getString(charNode *start) { addElement(&start, "Dog"); addElement(&start, "Androd"); addElement(&start, "Bat"); sort(start); printList(start); } void addElement(charNode **start, char *petName) { charNode *temp,*prev, *loc; int i; temp = newNode(petName); if (*start == NULL) { *start = temp; } else { loc = *start; prev = NULL; for (i=0; loc != NULL; i++) { prev = loc; loc = loc->next; } if (prev == NULL) { *start = temp; } else { prev->next = temp; } } } charNode* newNode(char *petName) { charNode *temp; temp = (charNode *) malloc(sizeof(charNode)); if (temp == NULL) { printf("WARNING - Memory allocation error\n"); exit(EXIT_FAILURE); } strcpy(temp->petName, petName); temp->next = NULL; return temp; } void printList(charNode *start) { while (start != NULL) { printf("%s\n", start->petName); start = start->next; } } void swap(charNode **a, charNode **b) { charNode *temp; temp = *a; *a = *b; *b = temp; } charNode *sort(charNode *start) { charNode *prev = NULL, *temp = NULL; charNode *current = NULL; if(start == NULL || start->next == NULL) { // have you tried this?? return start; } prev = current; current = start->next; while (current != NULL) { printf("%p %p %p %p\n", prev, current, temp, start); if ( strcmp(current->petName, prev->petName) < 0) { swap(&current, &prev); // I'm not sure about this, try it } prev = current; current = current->next; } return start; }

ok, try again, i've modified the code above

yes it works but its still unsorted:

Dog
Androd
Bat

i used the same exact code except for:

swap(&current, &prev); // I'm not sure about this, try it

even afte i modified:

start = sort(start);
printList(start);

so the i get a reference to the new list after its sorted.

what happened when you used my exact original code?? compiler error?

can you paste me the exact output and with the corrected code output?

im getting there i think :D

Code:

charNode *sort(charNode *start) { charNode *prev = NULL, *temp = NULL; charNode *current = NULL; if(start == NULL || start->next == NULL) { // have you tried this?? return start; } current = start->next; prev = current; while (current != NULL) { printf("%p %p %p %p\n", prev, current, temp, start); if ( strcmp(current->petName, prev->petName) < 0) { swap(&current, &prev); // I'm not sure about this, try it } prev = current; current = current->next; } return start; }

warning passing arg 1 of 'swap' from an incompatible pointer type
warning passing arg 2 of 'swap' from an incompatible pointer type

(hence why i provided the address the swap)

but i compiled it anyway and it crashed:

00000000 003D2C78 00000000 003D2C60

refer to my msg above (we should avoid posting more message :D, it's 3 pages already :D :p)

Ok, here's how to swap correctly. Assume you're trying to swap 2 nodes, a and b, from a singly linked list LList :

1) swap a->next and b->next correctly (Make sure you're actually swapping the addresses)
2) find the predecessors of a and b. Call them P(a) and P(b), respectively. You can find the predecessor of a node a in the Linked List LList doing this :

Code:

Node pred(Node * a, Node*List) { if(a == List){return NULL;} if((*a) == (*List).next) { return *List; } else { if((*List).next == NULL) { printf("Not in list."); } else { return pred(a,(*List).next); } } }

3) Swap the next pointer of the predecessors accordingly.

After that, you've swapped your nodes in your list correctly. Right now, you're not swapping correctly, so sorting, NO MATTER WHAT, will almost never work.

Quote:

Originally Posted by Happy_Reaper

Ok, here's how to swap correctly. Assume you're trying to swap 2 nodes, a and b, from a singly linked list LList :

1) swap a->next and b->next correctly (Make sure you're actually swapping the addresses)
2) find the predecessors of a and b. Call them P(a) and P(b), respectively. You can find the predecessor of a node a in the Linked List LList doing this :

Code:

Node pred(Node * a, Node*List) { if(a == List){return NULL;} if((*a) == (*List).next) { return *List; } else { if((*List).next == NULL) { printf("Not in list."); } else { return pred(a,(*List).next); } } }

3) Swap the next pointer of the predecessors accordingly.

After that, you've swapped your nodes in your list correctly. Right now, you're not swapping correctly, so sorting, NO MATTER WHAT, will almost never work.

ouch... you ruined the fun :D ...

Quote:

Originally Posted by yxunomei

ouch... you ruined the fun :D ...

Perhaps, but it's pointless to try and explain sorting if he can't swap right.

Happy_Reaper,

with your code im having trouble with the following lines:

Code:

if( (*a) == (*List).next) { return *List; }

error: invalid operands to binary ==

if( (*a) == (*List).next)

If you were to understand what I was doing, you'd know what I'm doing wrong. Anyhow, it's supposed to be a, not (*a)

ok...

i ran it like this:

swap(&start, &start->next, start);

Code:

void swap(charNode **a, charNode **b, charNode *start) { charNode *temp; charNode *preA = pred(start->next, start); charNode *preB = pred(start, start); preB = preA; temp = *a; *a = *b; *b = temp; }

and

Code:

charNode *pred(charNode *a, charNode *List) { if(a == List) { //printf ("BLAH"); return NULL; } if( a == (*List).next) { return List; } if((*List).next == NULL) { printf("Not in list."); } else { printf("RETURNED"); return pred(a,(*List).next); } }

it just returns

Androd
Bat

Dog is still missing...

original list:

Dog
Androd
Bat

For one thing, you're not swapping the pred pointers right. You have to swap (preA.next) and (preB.next) (see my above comment, where I gave you instructions)

Also, you're missing the point. Swap won't sort the list for you. It'll just change the positions of two nodes in your linked list without breaking the structure.

changed:

Code:

preB = preA;

to :

Code:

preA->next = preB->next;

now it just crashes *dies*

Quote:

Also, you're missing the point. Swap won't sort the list for you. It'll just change the positions of two nodes in your linked list without breaking the structure.

it does break the structure does it not? i mean i previously had 3 nodes but after swap runs im left with 2.

Quote:

Originally Posted by Axel

it does break the structure does it not? i mean i previously had 3 nodes but after swap runs im left with 2.

It shouldn't. You've not swapping preA and preB, you're just assigning preA to preB. That makes them both equal. Not a good idea in a linked list.

ok so you mean i should also run the swap method on the precedent nodes as well?

i.e.:

Code:

swap(&preA->next,&preB->next, start);

because now the list is just empty.

well i've tried doing things on paper and it makes sense. but when i apply it like below:

Code:

temp = *a; *a = *b; temp2 = *b; *b = temp; (*b)->next->next = temp2;

it doesn't. the last node is *still empty*

No. You see how you have a temp variable there when you swap a and b ? What is that temp node for ?

Now do the same thing for preA.next and preB.next.

you mean something like this?

Code:

void swap(charNode **a, charNode **b, charNode *start) { charNode *temp, *preTemp; charNode *preA = pred(start->next, start); charNode *preB = pred(start, start); preTemp = preA; temp = *a; *a = *b; *preB = *preA; *b = temp; preB = preTemp; }

*CRASH*

this is killing me :|

No, like this :

Code:

charNode* temp2 = (*preA).next; (*preA).next = (*preB).next; (*preB).next = temp2;

Code:

void swap(charNode **a, charNode **b, charNode *start) { charNode *temp, *preTemp; charNode *preA = pred(start->next, start); charNode *preB = pred(start, start); charNode* temp2 = (*preA).next; temp = *a; *a = *b; *b = temp; (*preA).next = (*preB).next; (*preB).next = temp2; }

*CRASH*

Oh for chrissakes.

Code:

void swap(charNode *a, charNode *b) { char temp; size_t i; for (i = 0; i < 12; i++) { temp = a->petName[i]; a->petName[i] = b->petName[i]; b->petName[i] = temp; } }

zx-1, i was just about to post the progress i made. The only problem was that the solution could only swap start and next node. Your solution however if i input any node it swaps it..hmm

i.e.:

Code:

void *swap(charNode **start, charNode *a, charNode *b) { charNode *d = a->next->next->next; a->next = b->next; b->next->next = b; b->next= d; }

actually your solution doesnt swap the nodes at all but just the contents of the struct which is cheating? you also don't need that for loop. it works fine without it.

so i'm guessing its not possible to have a function like the one you have there that swaps the nodes and reconstructs the list? is it too complex? because i can swap the nodes if i know where they are but as soon as i try it on the middle node and the next for example it stuffs up the list.

i.e.:

works fine for swapping start and the next node.

Code:

charNode *d = a->next->next; charNode *head = start; a = b; b->next = head; b->next->next=d;

this works fine for swapping the node after next and the one after next,next.

Code:

charNode *d = a->next->next->next; a->next = b->next; b->next->next = b; b->next= d;

but i cant seem to make a unified solution that does swapping regardless of the possition ?!?

Also, you have to swap the next pointer of each of the nodes you're swapping. I don't know why I didn't think of that. But that's important too. Also, you could very well just use zx-1's solution. It'll get the job done.

yea agreed... it's better to actually swap the physical string than to modify the pointer :D

I've always preferred to swap the the pointers around, as it just seems logical for me. But moving data accross nodes would work the same.

Also, it's easy right now to just copy over an array, but when your structs start containing a little more data, you'll be spending a lot of time copying everything over...