Insertion Sorted Linked List

[aph3x]

hello everyone, long time no... erm, post :)

as an assignment, im trying to sort a linked list using the insertion sort algorithm. sorting by swapping node values is trivial, however, i have to sort the list by manipulating the pointers of each node :eek:

the data being sorted is a paragraph from my data structures text. i have stored the paragraph in an array. i parse the paragraph and store each word in each struct's value array. each node has a previous pointer and a next pointer named plink and nlink, respectively.

the following code sorts the list, but for some reason it drops words (structs) from the list, and i can figure out why :confused: hopefully someone can help me find the bug...

head, temp, and this are pointers to a node structure.

head points to the first dynamically allocated node... below is code for how im currently implementing the insertion sort by pointer value



this = head->nlink;

for(i=1; this->nlink != 0x00; i++)
{
temp = this;
this = this->nlink;

j = i - 1;

while(j>=0 && (strncmp(temp->value, temp->plink->value, 24) < 0))
{
temp->plink->nlink = temp->nlink;
temp->nlink->plink = temp->plink;

temp->nlink = temp->plink;
temp->plink = temp->plink->plink;

temp->nlink->plink = temp;

if(temp->plink == 0x00)
{
head = temp;
break;
}

j--;
}


}

printf("\n\n\t\t\t -==[ Sorted Paragraph Text ]==-\n\n");

for(this=head; this->nlink != NULL; this=this->nlink)
printf("%s ", this->value);



if anyone needs ALL the code, let me know... TIA :)

[Stuka]

What I learned in my data structures class was to make a drawing of what actually needs to happen, and in what order, to avoid losing a pointer. That method serves me quite well, and helps me maintain my sanity - I highly recommend it!

[marvin]

if(temp->plink == 0x00)
{
/* No previous node, make this node head of list */
head = temp;
break;
}
else
{
/* Set the new previous node's next pointer to point at this node */
temp->plink->nlink = temp;
}


You forgot to update the "new previous" node's next pointer.

Btw, you will need to modify your code slightly in order to sort the last element in the list.

[aph3x]

marvin... you da man! :)

that was the bug, and i didnt even have to modify the code for the last node, everything sorted fine :)

ill buy you a beer next time youre in dallas :p

thanks again

[marvin]

What happens if you try to sort a list having only two elements, "A" and "B" holding the strings "alpha" and "bravo" in the wrong order... I.e. the list should print as "bravo alpha" before you sort it

[aph3x]

i tried that and it still works...

node 1 contains bravo and node 2 contains alpha. after sorting is complete, the list is printed from head to tail and displays alpha bravo in that order. :)

[marvin]

Originally posted by aph3x:
<STRONG>i tried that and it still works...

node 1 contains bravo and node 2 contains alpha. after sorting is complete, the list is printed from head to tail and displays alpha bravo in that order. :)</STRONG>

Ok, but when I read the code it looks like it won't :confused:

The list will look something like

NULL &lt;- (head) B &lt;-&gt; A -&gt; NULL

before it is sorted.

In you code you set this to head-&gt;nlink which is A. Then you check in your for loop if this-&gt;nlink != NULL since this equals A and A-&gt;nlink equals NULL it will not sort anything.

What am I missing?

[aph3x]

i dont know, but im missing it too...

it works, thats what gets me an A in data structures, and thats all that matters, for now :)