Sort Linked List alphabetically

Question

I'm trying to sort my list alphabetically but i'm having some issues. I have the following:

    struct listNodeData
        {
            int value;
            char *position;
            char *lastName;
            struct listNodeData * next;
        };
        typedef struct listNodeData listNodeData;

void sortList(listNodeData *List)
{
    int swapped;
    listNodeData *ptr1;
    listNodeData *lptr = NULL;

    do
    {
        swapped = 0;
        ptr1 = List->next;

        while (ptr1->next != lptr)
        {
            if (strcmp(ptr1->lastName,ptr1->next->lastName) > 0)
            {
                swap(ptr1,ptr1->next);
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    }
    while (swapped);

}

void swap (listNodeData *a,listNodeData *b)
{

    char *lastName = malloc(sizeof(char) * 20);
    strcpy(lastName,a->lastName);
    strcpy(a->lastName,b->lastName);
    strcpy(b->lastName,lastName);

}

I am trying to sort the linked list by last name. Right now i'm just trying to swap the last names of my nodes before worrying about swapping the value and position along with the last name. When I compile my program, it works when I run it I get Bus error 10.

I'm not exactly sure why im getting bus error. I've looked at it, and it might have something to do with my strcmp? I'm not sure why because i malloced lastName when I initialized my node, and am mallocing inside the swap function.

The linked list has a dummy header node, so thats why I have ptr1 = List->next instead of ptr1 = List

listNodeData *initNode(int number,char *lastName,char *position)
{
    listNodeData *newNode;
    newNode = malloc(sizeof(listNodeData));
    newNode->position = malloc(sizeof(char) * 20);
    newNode->position = position;
    newNode->lastName = malloc(sizeof(char) * 20);
    newNode->lastName = lastName;
    newNode->value = value;
    newNode->next = NULL;
    return (newNode);
}

Just side note: you don't need line `typedef struct listNodeData listNodeData;`, you already have type `listNodeData` defined as `struct` above — mvidelgauz, Jul 01 '16 at 19:27
Another side note. It would be hard to find a less efficient way to sort a collection of pointers. Think about how many times the entire list must be traversed to accomplish the sort. Every time a single node is swapped, `swapped = 1;` and the entire list must be traversed again. For a few nodes, it doesn't matter, but for millions the sort will be very slow. Look into assigning the node pointers to an *array of pointers* and calling `qsort` as an alternative. — David C. Rankin, Jul 23 '16 at 06:15

Dennis Shtatnov · Accepted Answer · 2016-07-01T19:28:04.697

1

In you initialization code,

newNode->lastName = malloc(sizeof(char) * 20);
newNode->lastName = lastName;

This does not use the buffer you malloc'ed. Instead it replaces the pointer to the buffer with the lastName given to the function. Use a strcpy to move the lastname into the buffer:

strcpy(newNode->lastName, lastName);

Note: Similarly there is the same issue with the position property so this needs to be done for both.

Some other issues to note:

Don't forget to free(lastName) at the end of swap to not produce a memory leak in the swap

edited Jul 01 '16 at 19:28

answered Jul 01 '16 at 19:25

Dennis Shtatnov

1,333
11
17

Completely forgot about that! I'll try that right now – FreeStyle4 Jul 01 '16 at 19:27
@FreeStyle4 - since lastName is only 20 characters, you could allocate off the stack using _alloca() or alloca() (name depends on compiler), no free() is needed in this case. Since the program is not recursive or reentrant, you could just declare lastName as static (as a static array). – rcgldr Jul 01 '16 at 23:56

score 0 · Answer 2 · edited Jul 23 '16 at 05:14

0

There is no space allocated for the string in swap function.

Try this:

char*  lastName = (char*) malloc(20*sizeof(char));

edited Jul 23 '16 at 05:14

Pang

9,564
146
81
122

answered Jul 01 '16 at 19:31

amrender singh

7,949
3
22
28

Do *NOT* cast the return of `malloc`. It is totally unnecessary and can hide errors. See: [**Do I cast the result of malloc?**](http://stackoverflow.com/q/605845/995714) for thorough explanation. `char *lastname = malloc (20 * sizeof *lastname);` is all that is needed. – David C. Rankin Jul 23 '16 at 06:09

Sort Linked List alphabetically

2 Answers2