How to sort linked list

Question

I am trying to sort a linear linked list by last name, however it is crashing, also i don't know if my algorithm is working correctly.

Can someone help me to stop it from crashing, and see if my algorithm for sorting the list is working?

void sort(NODEPTR *employees, int maxEmployees)
{
  int i = 0, j = 0, k = 0;
  NODEPTR p, q, pTrail = NULL, qTrail, temp;
  temp = (NODEPTR) calloc(1, sizeof(node));

  qTrail = *employees;
  q = (*employees)->next;
  for (i = 0; i < maxEmployees; i++)
  {

    p = *employees;

    while (p != q)
    {

      if (strcmp(p->lastName, q->lastName))
      {
        temp = q;
        qTrail = q->next;
        q = pTrail->next;

        temp = pTrail->next;
        pTrail = temp;

        p = q;
      }
      else
      {
        pTrail = p;
        p = p->next;
      }

    }
    qTrail = q;
    q = q->next;

    pTrail = NULL;
  }
  printf("%10s %10ss\n", "First", "Last");
  printf("%10s %10s\n", "-----", "----");

  for (i = 0; i < maxEmployees; i++)
  {
    printf("%10s %10ss\n", (*employees)->firstName, (*employees)->lastName);
  }
}

Linked List:

typedef struct node
{
  char firstName[11];
  char lastName[16];
  char gender;
  int tenure;
  char rate;
  float salary;
  struct node *next;
} node, *NODEPTR;

Instead of switching the whole nodes with places you should switch just their content and leave the bindings untouched. Also would be nice to know what is your crash error. — Alexandru Barbarosie
– Alexandru Barbarosie, Commented Jul 5, 2013 at 9:35
@AlexandruBarbarosie But if the nodes are large, that would turn the program incredibly slow... — Lundin
– Lundin, Commented Jul 5, 2013 at 11:28
@Lundin well basicly yes, but in his case it is not that big. Furthermore it lacks the OP from committing any memory leaks. — Alexandru Barbarosie
– Alexandru Barbarosie, Commented Jul 5, 2013 at 11:33
@AlexandruBarbarosie: I feel switching the nodes is much more elegant as it make the algorithm independend of the nodes' payload*. — alk
– alk, Commented Jul 5, 2013 at 13:18

alk · Accepted Answer · 2013-07-05 13:23:05Z

2

Your logic seems to be wrong:

strcmp() will return three values.

1 if first argument's value is >
-1 if second argument's value is >
0 if both arguments's value are same.

So based on strcmp(p->lastName,q->lastName) you can not sort.

You should change the position only when strcmp() return 1. for -1 and 0 it should go in else part.

edited Jul 5, 2013 at 13:23

alk

71.2k10 gold badges112 silver badges274 bronze badges

answered Jul 5, 2013 at 9:53

Mayur Navadia

2411 silver badge4 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Vatine Over a year ago

No, never, ever, make the (rather invalid) assumption that strcmp returns only the values -1, 0 or 1. It is perfectly standards-conforming for strcmp("a", "c") to return -2.

This isn't my real name Over a year ago

More importantly, it is perfectly standards-conforming for strcmp("a","c") to return -97 (or -9000). The only guarantees you have about the return value are that it is an int, that it will be zero if the two strings are identical, that it will be nonzero if the two strings differ in any regard, and that... "The sign of a non-zero return value shall be determined by the sign of the difference between the values of the first pair of bytes (both interpreted as type unsigned char) that differ in the strings being compared.".

Collectives™ on Stack Overflow

How to sort linked list

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related