Bubble sort with linked list C

Question

My sort algorithm does not seem to work in some cases. I'm acting on a doubly linked list (with pointer on the previous and next ones). I submit the definition of my structure and the essential. I find myself with a infinite loop, with specific cases like this one. I use strcmp() function, to sort.

#include "string.h"
#include "stdlib.h"
#include "stdio.h"

typedef struct s_file {
    char    *name;
    struct s_file     *next;
    struct s_file     *previous;
} t_file;

void swap_files(t_file *file, t_file *next)
{
    t_file *previous;

    previous = file->previous;
    if (previous)
        previous->next = next;
    file->next = next->next;
    file->previous = next;
    if (next->next)
        next->next->previous = file;
    next->next = file;
    next->previous = previous;
}

static t_file *sort_files(t_file *files)
{
    t_file *file;
    t_file *next;

    file = files;
    while ((next = file->next))
    {
        if (strcmp(file->name, next->name) > 0)
        {
            swap_files(file, next);
            if (!next->previous)
                files = next;
            file = files;
            continue;
        }
        file = file->next;
    }
    return (files);
}

void debug(t_file *files)
{
    while (files)
    {
        printf("=> %s\n", files->name);
        files = files->next;
    }
}

int main(void)
{
    t_file second;
    t_file first;
    t_file third;

    first.name = "Poire";
    first.previous = NULL;
    first.next = &second;

    second.name = "Banane";
    second.previous = &first;
    second.next = &third;

    third.name = "Fraise";
    third.previous = &second;
    third.next = NULL;

    first = *(sort_files(&first));
    debug(&first);
    return (0);
}

Answer 1

The swap_files is overly complicated. It's perfectly adequate to just swap the data:

void swap_files(t_file *file, t_file *next)
{
    char *tmp = file->name;
    file->name = next->name;
    next->name = tmp;
}

And guess what? It solved the problem.

It was mentioned two issues with this solution in comments below, and I'd like to address them. First, this code could be less efficient if there are many data fields and second, chances are that you forget a field.

1. It's very unlikely that this would be the bottleneck, and if it is, deal with it then and not before. And when there is only one field, this code is much more effective. Arguing against a certain method because it would be slower if the circumstances were different is not a good argument.

2. Forgetting a field is a strong case against this. I have no objections there.

A solution to both above is to create a second struct for the data, like this:

struct data {
    char * name;
    int age;
    char * address;
    /* More fields */
}

struct s_file {
    struct data *data;
    struct s_file *next;
    struct s_file *previous;
}

You could argue for or against this. In a way it doesn't "feel like C", but on the other hand you get a nice separation on responsibilities.

Answer 2

You should definitely not overwrite first with the new head node of the list, because doing this causes the list to be corrupted. Just define a pointer to hold it:

    t_file *head = sort_files(&first);
    debug(head);

Also do not use " for standard header files:

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

Finally, even with these fixes, your bubble sort algorithm seems incorrect: when you swap the nodes at file and next, you should backtrack to the previous node just in case the next node was smaller than the previous node too.

Here is a corrected version:

static t_file *sort_files(t_file *head) {
    t_file *file;
    t_file *next;

    file = head;
    while ((next = file->next) != NULL) {
        if (strcmp(file->name, next->name) > 0) {
            swap_files(file, next);    // swap the nodes linkage
            file = next;               // next is now before file
            if (file->previous) {
                file = file->previous; // backtrack to the previous node
            } else {
                head = file;           // save the new head of list
            }
        } else {
            file = file->next;
        }
    }
    return head;
}