3
\$\begingroup\$

(See the initial iteration.)

Continuing from Merge sorting a singly-linked list in C, I have incorporated the points made by @vnp.

Now it looks like this:

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

typedef struct linked_list_node {
    int value;
    struct linked_list_node* next;
} linked_list_node;

/*******************************************************************************
* This fuction converts the command line arguments to a linked list.           *
*******************************************************************************/
static linked_list_node* build_linked_list_from_args(int argc, const char* argv[])
{
    if (argc <= 1)
    {
        return NULL;
    }

    linked_list_node* list = calloc(argc - 1, sizeof(*list));

    for (size_t node_index = 0; node_index < argc - 1; ++node_index)
    {
        list[node_index].value = atoi(argv[1 + node_index]);
        list[node_index].next  = node_index == argc - 2 ?
                                    NULL :
                                    &list[node_index + 1];
    }

    return list;
}

/*******************************************************************************
* This function prints the entire linked list to stdout.                       *
*******************************************************************************/
static void print(linked_list_node* head)
{
    printf("[");
    linked_list_node* current_node = head;

    if (current_node)
    {
        printf("%d", current_node->value);
        current_node = current_node->next;
    }

    while (current_node)
    {
        printf(" %d", current_node->value);
        current_node = current_node->next;
    }

    printf("]");
}

/*******************************************************************************
* This function merges stabily the two input lists that are expected to be     *
* sorted.                                                                      *
*******************************************************************************/
static linked_list_node* merge(linked_list_node* left_head,
                               linked_list_node* right_head)
{
    linked_list_node* merged_list_head;
    linked_list_node* merged_list_tail;

    if (right_head->value < left_head->value)
    {
        merged_list_head = right_head;
        merged_list_tail = right_head;
        right_head = right_head->next;
    }
    else
    {
        merged_list_head = left_head;
        merged_list_tail = left_head;
        left_head = left_head->next;
    }

    while (left_head && right_head)
    {
        if (right_head->value < left_head->value)
        {
            merged_list_tail->next = right_head;
            merged_list_tail = right_head;
            right_head = right_head->next;
        }
        else
        {
            merged_list_tail->next = left_head;
            merged_list_tail = left_head;
            left_head = left_head->next;
        }
    }

    merged_list_tail->next = left_head ? left_head : right_head;
    return merged_list_head;
}

/*******************************************************************************
* This function splits the input linked list in two sublists and returns the   *
* head of the right one.                                                       *
*******************************************************************************/
static linked_list_node* split(linked_list_node* head)
{
    linked_list_node* slow = head;
    linked_list_node* fast = head;
    linked_list_node* prev_slow = NULL;

    while (fast && fast->next)
    {
        prev_slow = slow;
        slow = slow->next;
        fast = fast->next->next;
    }

    linked_list_node* right_sublist_head = prev_slow->next;
    prev_slow->next = NULL;
    return right_sublist_head;
}

/*******************************************************************************
* This function implements the actual sorting routine.                         *
*******************************************************************************/
static linked_list_node* sort_impl(linked_list_node* head)
{
    if (!head->next)
    {
        return head;
    }

    linked_list_node* right_sublist_head = split(head);
    return merge(sort_impl(head), sort_impl(right_sublist_head));
}

/*******************************************************************************
* This function sorts the input linked list whose the first node is 'head'.    *
*******************************************************************************/
linked_list_node* sort(linked_list_node* head)
{
    if (!head || !head->next)
    {
        return head;
    }

    return sort_impl(head);
}

int main(int argc, const char * argv[]) {
    linked_list_node* head = build_linked_list_from_args(argc, argv);
    print(head);
    puts("");
    head = sort(head);
    print(head);
    puts("");
    return 0;
}

As always, any critique is much appreciated.

\$\endgroup\$
7
\$\begingroup\$
  1. Utilize const to indicate the referenced data is not changed and allow optimizations.

    // static void print(linked_list_node* head)
    static void print(const linked_list_node* head)
    
  2. In print(), code repeated all for the sake of a " ". Suggested simplification:

    const char *sep = "";
    while (current_node) {
        printf("%s%d", sep, current_node->value);
        sep = " ";
        current_node = current_node->next;
    }
    
  3. I'd expect non-static function names tailored to linked lists. Example: sort() is too likely to collide with other code.

    // linked_list_node* sort(linked_list_node* head)
    linked_list_node* linked_list_sort(linked_list_node* head)
    
  4. Many functions are static. None of these should be in the same .c file as main(). Better to have all linked list functions in a file like linked_list.c with a corresponding linked_list.h header file.

  5. Expect more that just sort() to not be static. Certainly build_linked_list_from_args() is meant to be visible.

  6. Consider a call like merge(list1, list1). Will code work? If that functionality is not needed, use restrict to indicate that and allow more optimizations.

    // linked_list_node* merge(linked_list_node* left_head, linked_list_node* right_head)
    linked_list_node* merge(linked_list_node* restrict left_head, 
        linked_list_node* restrict right_head)
    

Minor

  1. Spelling fuction --> function.

  2. sizeof(*list) can be coded simpler as sizeof *list. (style issue)

  3. Not a fan of using printf(string) to print strings. printf() expects that first argument to point to a string used as a format - which is a problem should it contain "%". Consider fputs(string, stdout)

  4. Uncertain that const is generally OK in main(). Since it is test code, suggest simplifying.

    // int main(int argc, const char * argv[])
    int main(int argc, char * argv[])
    
  5. Add date and your ID (name) to the file as a comment.

  6. Format: The below format is hard to maintain with automatic formatting tools (at least mine). Maybe it does well with yours. Formatting is a pain and should not be maintained manually. Assuming you did not use such a tool, try one.

    static linked_list_node* merge(linked_list_node* left_head,
                                   linked_list_node* right_head)
    

[Edit]

Simplified merge(), only while() loop needed.
Down-side: need a linked_list_node variable and not just a linked_list_node *.

static linked_list_node *merge(linked_list_node *left, linked_list_node *right) {
  linked_list_node head;  // Only use next field
  linked_list_node *tail = &head;

  while (left && right) {
    if (right->value < left->value) {
      tail->next = right;
      tail = right;
      right = right->next;
    } else {
      tail->next = left;
      tail = left;
      left = left->next;
    }
  }

  tail->next = left ? left : right;
  return head.next;
}
\$\endgroup\$
1
\$\begingroup\$

Readability regarding docstrings:

You've written docstrings to describe your functions as following: "This function [describes what the function does]".

/*******************************************************************************
* This function splits the input linked list in two sublists and returns the   *
* head of the right one.                                                       *
*******************************************************************************/
static linked_list_node* split(linked_list_node* head)



/*******************************************************************************
* This function sorts the input linked list whose the first node is 'head'.    *
*******************************************************************************/
linked_list_node* sort(linked_list_node* head)

Beginning every docstring with "This function" is redundant and hurts readability. Any potential reader knows that the subject of the comment is a function. Instead:

/*******************************************************************************
* Splits the input linked list in two sublists and returns the
* head of the right one.                                                       *
*******************************************************************************/
static linked_list_node* split(linked_list_node* head)



/*******************************************************************************
* Sorts the input linked list whose the first node is 'head'.
*******************************************************************************/
linked_list_node* sort(linked_list_node* head)

It may seem petty but if the reader was scanning between a large number of docstrings, it makes a significant difference in how quickly and easily distinguishable they are.

\$\endgroup\$
0
\$\begingroup\$

If performance is one of the goals for a linked list sort, then a bottom up merge sort using a small (26 to 32) array of pointers to nodes is a much faster method, than using an array oriented top down approach which requires repeated scanning of sub-lists (to emulate random access iterators) in order to split them in half.

Wiki psuedo code:

http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

I can add example C code if interested.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.