Sorting a Linked List

[kimhoong79]

Hi, I am still in learning phrase on this matter. I have written a program to allow user to enter album's title and singer. I will then insert these information into a Linked List. After insertion and any other tasks, I will sort the Linked List. I think I wrote the sorting code correctly but it's still not working well. Please give comment. Here's the code:

void Sort(NodePtr *L, int criteria)
{
NodePtr p, q;

for(p=*L; p->Link!=NULL; p=p->Link)
for(q=p->Link; q->Link!=NULL; q=q->Link)
switch(criteria)
{
case 1:
if (strcmp(p->title,q->title)==1)
ChangeNode(&p,&q);
break;
case 2:
if (strcmp(p->singer,q->singer)==1)
ChangeNode(&p,&q);
break;
}
}

void ChangeNode(NodePtr *p, NodePtr *q)
{
NodePtr temp;

temp=(NodePtr)malloc(sizeof(NodeType));

CopyNode(&temp,p);
CopyNode(p,q);
CopyNode(q,&temp);

}

void CopyNode(NodePtr *temp, NodePtr *x)
{
strcpy((*temp)->title,(*x)->title);
strcpy((*temp)->singer,(*x)->singer);
(*temp)->price = (*x)->price;
(*temp)->year = (*x)->year;
}

 

[kimhoong79]

I have been looking at this code for 2 days and finally I got the solution (or maybe should I say the mistake?)

Actually I got both for-loop condition wrong. The first one should NOT be for(p=*L; p->Link!=NULL; p=p->Link), the correct one should be for(p=*L; p!=NULL; p=p->Link). For the second for-loop, the mistake is exactly the same. The correct second for-loop should be for(q=p->Link; q!=NULL; q=q->Link)


I guess everyone's having holiday in Christmas, that's why no one is replying me. Anyway, Merry Christmas and Happy New Year!

 

[mingis]

Here is also free(temp); missing at the end of ChangeNode();

And why do you use pointers to NodePtr's in arguments, though you are not assigning anything to them? Why not
void Sort(NodePtr L, int criteria);
void ChangeNode(NodePtr p, NodePtr q);
void CopyNode(NodePtr temp, NodePtr x);?

Just 15 minutes ago I began to think about how to sort my linked list. If you are not against, I will use your algoritm, OK? (though it is not a kind of qsort())

 

[kimhoong79]

I'm using pointers to NodePtr's in arguments because I consider them as output parameters since I'm changing the values in the nodes. Correct me if I was wrong, ok?

It's my pleasure that someone is appreciating my code since I'm a kind of a newbie in this linked-list. Yes, you may use my algorithm.

 

[ArkM]

Alas, there are at least 3 errors in this sort routine:
1. Don't forget free(temp) in ChangeNode() - or better (and simpler use local (automatic) variable

NodeType temp; /* instead of NodePtr with malloc/free */

2. strcmp() returns positive value (not 1) if 1st arg > 2nd arg (see strcmp() library function specification).
3. Right reference to node member:

NodePtr x;
x->price /* Not (*x)->price */

You can't compile this incorrect code of CopyNode()...

There are (at least) 2 weaknesses in this sort routine:
1. Try split your bubble sort loops for criteria == 1 and criteria == 2, don't check this condition in the N-square loop. The bubble sort is a rather slow method, avoid redundant overheads...
2. List power is a capability to manipulate with nodes without memory overheads (change a pointers, not a node as is). This implementation can't do that (see CopyNode). Can you sort dynamically allocated nodes with dynamic strings? No, you can't...

 

[kimhoong79]

ArkM,

Thanks for your comment. Anyway, I'm currently using this code and do not get any problem.

(1)Yes, you are right. I should free(temp)

(2)strcmp returns positive value (not 1) - for this point, I'm quite convinced because from what I learnt, strcmp will only return either 1, 0 or -1 only. Anyway, correct me if I was wrong.

(3)I think for this one I've got it correctly because when I declare the x, I declare it by NodePtr *x, which mean it's a pointer to a Node Pointer, so when I need to refer to the node's data, I will need to use (*x)->something

For the final 2 comments, I am totally agreed with you.

Thanks for your comments once again.

ps: I'm still new in this, so I might be a bit naive,

 

[DaveSinkula]

(2)strcmp returns positive value (not 1) [red]- for this point, I'm quite convinced because from what I learnt, strcmp will only return either 1, 0 or -1 only. Anyway, correct me if I was wrong.[/red]

#include <stdio.h>
#include <string.h>

int main(void)
{
   char hello[] = "hello", world[] = "world";
   int result = strcmp(hello, world);
   printf("result = %d\n", result);
   return 0;
}

/* my output
result = -15
*/

 

[chipperMDW]

[tt]strcmp[/tt] returns positive, negative, or zero. From the man(ual) page:

The [tt]strcmp()[/tt] function returns an integer less than, equal to, or greater than zero if s1 is found, respectively, to be less than, to match, or be greater than s2.


Now, a certain implementation of [tt]strcmp[/tt] might return 1, 0, and -1. That might be your implementation.

But what happens when your system gets updated and the [tt]strcmp[/tt] has been fitted with an extension that lets it return more information about the comparison (for example)?

Your program would magically break.

So write your program according to what the manual says should happen (<, >, or = 0), not the specific instance of that behavor that your system seems to exhibit (1, -1, or 0).

 

[kimhoong79]

I tried DaveSinkula's code (directly copy-n-paste), the answer I got was -1. FYI, I'm using Ms Visual C++ 6.0

Although I'm still getting -1, I am convinced that the correct way should be what you two had shown me. It is because I am using Win Xp, I never consider other OS like Linux or Unix.

Actually, I got this information int some lecture notes from my friend. I thought it is reliable, but it turns out not.

Thanks for the explainations.

 

[ArkM]

See true list sorting improvisation (it's freeware:

#define TSZ 32       /* for example only */

typedef struct _Node /* for example only */
{
  struct _Node* link;
  char title[TSZ];
} Node, *PNode;

typedef int (*PFC)(const void* p1, const void* p2);

static int StrCmpIncr(const void* p1, const void* p2)
{
return strcmp(((const PNode)p1)->title,
              ((const PNode)p2)->title);
}

static int StrCmpDecr(const void* p1, const void* p2)
{
  return -strcmp(((const PNode)p1)->title,
                 ((const PNode)p2)->title);
}
/* Bubble sort common implementation */
PNode SortList(PNode plist, PFC cmpfun)
{
  PNode p1st = plist;
  PNode pprev;
  PNode plast = 0;
  PNode p;
  int    more  = 1;

  if (!plist)
     return plist;
  if (!cmpfun)
     cmpfun = StrCmpIncr;

  while (more)
  {
    more = 0;
    pprev = 0;
    for (p = p1st; p->link && p->link != plast;)
    {
      if (cmpfun(p,p->link) > 0)
      {
         more = 1;
         if (pprev)
            pprev->link = p->link;
         else
            p1st = p->link;
         pprev = p->link;
         p->link = p->link->link;
         pprev->link = p;
      }
      else
      {
         pprev = p;
         p = p->link;
      }
    }
    plast = p;
  }

  return p1st;
}

PNode SortListOrd(PNode plist, int order)
{
  return SortList(plist,order >= 0?StrCmpIncr:StrCmpDecr);
}

PNode SortTree(PNode* ptree, int order)
{
  return ptree?(*ptree = SortListOrd(*ptree, order)):0;
}

 

[Salem]

> I tried DaveSinkula's code (directly copy-n-paste), the answer I got was -1.
The standard only states <0, ==0 and >0
Both results are consistent with this specification.

--

 

[dchoulette]

Some reflexions about strcmp returning <0, =0, >0 instead of -1, 0, 1.

As Salem said: both results are consistent, yes. But looking for positive or negative instead of 1 and -1 is more generic and will be true for all implementations. When in doubt stick to the manual.

How many times did I found old software crashing with a new OS or library version ? The developpers generally arguing the new OS or library version was not backward compatible. But when looking in the code you could find free interpretations of function specification that just happened to be working in a specific version.

The manual for strcmp says <0, =0, >0 (even on Visual C++, see

http://msdn.microsoft.com/library/d...html/_crt_strcmp.2c_.wcscmp.2c_._mbscmp.asp).

Checking for -1, 0, 1 is a free interpretation.

Besides, it can also be slower, as far as I can remember how processors do their tests (or how the processors I worked with, did their tests in the late 80's ).

Basically, to compare a value to 1, the processors substract(ed) 1 from the value then check(ed) to see if the result is(/was) positive, negative or null. You'd do better by just checking for positive value so avoiding the substraction.

Even for new processors (that I do not know that well), I can't think of any reason why checking for a positive value could be slower than checking equality to 1.

So, you could have a more generic and universal test of strcmp result that is also faster !

You are in the inner loop of a sort algorithm, any gain can prove substantial.

Comments welcome.

--------------------

Denis

 

[ArkM]

dchoulette:
Exactly. Excellent.

 

[kimhoong79]

I was about to submit my comment yesterday when my connection was broken down, sigh.

Overall, I am convinced that strcmp should return >0, 0 or <0 instead of the absolute 1,0 or -1.

Thanks for all the efforts explaining.

 

[jstreich]

C99 standards say negitive, 0 , positive; so there may be implementations where strcmp/strncmp/strcasecmp/et. al return a subtraction, and yeild results other than -1, 0, 1.