2
\$\begingroup\$

I previously implemented a Merge Sort for arrays, so after fixing up my code for the array-based merge sort I have now implemented a merge sort for a basic singly-linked list data structure which only contains the pointer to the data and a pointer to the next "Node". I have tried to use the advice given on the previous post (/q/260010) to help in my endeavor this time around. There are three things I did not change in my current code or my previous code; let me explain my reasoning:

  1. Deceleration Declaration and initialization of variables are done separately as I use C90, from habit.
  2. I am used to using the <stdint.h> header to write all my code using fixed-width types, so I usually use that for the functions such as merge_sort as for it to stay consistent across platforms. While the user code is written using "int", "short", "char" to emulate a sort of user code feel.
  3. I learned to use space for programming instead of tab, and we were told to do 3 spaces, how many space do you recommend 2, 3, 4, or X amount?

Any advice on how to improve my code will help; hopefully this implementation is much better as I have read up online and have been informed that merge sort is usually preferred for linked list and large sets of data.

TLDR - please advise on how to improve my implementation of merge sort for the linked list version. And how many spaces do you use for indentation?

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

struct Node{
   void *data;
   struct Node* next;
};

/*triple ref pointer are really cool as you don't need two pointers*/
int32_t split_list(struct Node *current, struct Node **front, struct Node **middle)
{
   uint32_t length, length_of_middle;
   struct Node *current_temp = current;
   struct Node **triple_ref = &current;

   if(current == NULL)
   {
      *front = *middle = NULL;
      return -1;
   }

   *front = current;
   *middle = current;
   length = length_of_middle = 0;

   while(current_temp != NULL)
   {
      current_temp = current_temp->next;
      length++;
   }

   while(length_of_middle < length / 2)
   {
      triple_ref = &((*triple_ref)->next);
      length_of_middle++;
   }

   *middle = *triple_ref;
   *triple_ref = NULL;

   return 0;
}

int32_t merge_sort(struct Node **head, int compare(const void *, const void *))
{
   struct Node *front, *middle;
   struct Node temp;
   struct Node *current = &temp;

   if(head == NULL)
   {
      return -1;
   }
   else if((*head)->next == NULL)
   {
      return 0;
   }

   split_list(*head, &front, &middle);

   merge_sort(&front, compare);
   merge_sort(&middle, compare);

   while(front != NULL && middle != NULL)
   {
      if(compare(front, middle) <= 0)
      {
         current->next = front;
         front = front->next;
         current = current->next;
      }
      else
      {
         current->next = middle;
         middle = middle->next;
         current = current->next;
      }
   }

   if(front != NULL)
   {
      while(front != NULL)
      {
         current->next = front;
         front = front->next;
         current = current->next;
      }
   }
   else
   {
      while(middle != NULL)
      {
         current->next = middle;
         middle = middle->next;
         current = current->next;
      }
   }

   *head = temp.next;
   return 0;
}


/*user code*/

int compare(const void *ptr1, const void *ptr2)
{
   const struct Node *node1, *node2;
   node1 = ptr1;
   node2 = ptr2;

   return *(int *)(node1->data) - *(int *)(node2->data);
}

void print_list(const struct Node *node)
{
   printf("\n");
   while(node != NULL)
   {
      printf("%d ", *(int *)(node->data));
      node = node->next;
   }
   printf("\n");
}

int32_t push_list(struct Node **head, void *val, const size_t size_of_element)
{
   struct Node *node;

   if(head == NULL)
   {
      return -1;
   }

   node = malloc(sizeof(*node));
   if(node == NULL)
   {
      return -1;
   }

   /*copy data*/
   node->data = malloc(size_of_element);
   if(node->data == NULL)
   {
      free(node);
      return -1;
   }
   memcpy(node->data, val, size_of_element);
   node->next = NULL;

   /*insertion*/
   if(*head != NULL)
   {
      struct Node *current;
      current = *head;
      while(current->next != NULL)
      {
         current = current->next;
      }
      current->next = node;
      return 0;
   }

   *head = node;
   return 0;
}

void free_list(struct Node *head)
{
   struct Node *temp;
   while(head != NULL)
   {
      temp = head;
      head = head->next;
      free(temp->data);
      free(temp);
   }
}

int main(void)
{
   struct Node *head;
   struct Node *front, *middle;
   int i;

   i = 10;
   /* i = 666;*/

   /*add values*/
   head = front = middle = NULL;
   for(; i > -1; i--)
   {
      push_list(&head, &i, sizeof(i));
   }
   i = 10;
   push_list(&head, &i, sizeof(i));
   i = -1;
   push_list(&head, &i, sizeof(i));

   /*print sort print*/
   print_list(head);
   merge_sort(&head, &compare);
   print_list(head);

   free_list(head);
   return 0;
}
\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

I learned to use space for programming instead of tab, and we were told to do 3 spaces, how many space do you recommend 2, 3, 4, or X amount?
And how many space do you use when programming?

This is a style issue and best to follow your group's coding standard which apparently is 3. I use 2.

A good coding environment allows you to change the indent on the entire file quickly with a set-up option and invoking that auto formatter.

If you are manually editing for the correct indentation, you are inefficient. Use an auto-formatter.


Deceleration ....

Whoa, slow down there 😉. Did you mean Declaration?


Namespace

Rather than

struct Node{
int32_t split_list()
int32_t merge_sort()
void print_list()
int32_t push_list()
void free_list()

Consider a uniform naming

struct DList {
int32_t DList_split()
int32_t DList_merge_sort()
void DList_print()
int32_t DList_push()
void DList_free()

Form a DList.h header file and segregate your DList functions into a DList.c file.

Weak compare

*(int *)(node1->data) - *(int *)(node2->data) risks UB and an incorrect result when the subtraction incurs overflow.

Instead:

int i1 = *(int *)(node1->data);
int i2 = *(int *)(node2->data);
return (i1 > i2) - (i1 < i2);

int vs. int32_t vs ....

I see little value is using int32_t here. Recommend reworking code to size_t for a type that relates to array indexing and int/bool for a simple success flag.

Minor: () not needed

Style issue:

// node = malloc(sizeof(*node));
node = malloc(sizeof *node);
\$\endgroup\$
2
  • \$\begingroup\$ Sorry, I fixed the typo in the question, spoiling your pun... \$\endgroup\$ Apr 28, 2021 at 6:59
  • \$\begingroup\$ Got it. I need to change my functions name for the linked list for it to be more consistent! By the way Nice pun, I do need to slow down. \$\endgroup\$
    – Dagar
    Apr 28, 2021 at 15:29
1
\$\begingroup\$
  • No naked loops. Every loop represents an important algorithm, and as such deserves a name. For example, the loops in split_list really are

      uint32_t list_length(struct Node *);
    

    and

      struct Node * advance(struct Node *, uint32_t);
    
  • split_list is a bit more complicated than necessary. The fact that front becomes current is known in advance. Do we really need to pass it?

    Similarly, I don't see the reason for triple_ref to be a ** (BTW, the name is really confusing - why triple?).

    All that said, consider

      struct Node * split_list(struct Node * current)
      {
          if (current == NULL) {
              return MULL;
          }
          uint32_t half_length = list_length(current) / 2;
          struct Node * pre_middle = advance(current, half_length);
          struct Node * middle = pre_middle->next;
          pre_middle->next = 0;
          return middle;
      }
    
  • I don't see the reason to for merge_sort to return an integer. This value is never tested anyway. It is much more natural to return head:

      struct Node * merge_sort(struct Node * head, int compare(const void *, const void *));
    
  • There is no need to loop over the unmerged remains of the lists. They are already good, and we don't care about current any more.

      if (front != NULL) {
          current->next = front;
      } else {
          current->next = middle;
      }
    
  • current = current->next is performed in both if and else branches of merging. Lift it out.

\$\endgroup\$
1
  • \$\begingroup\$ The reason I use the "triple_ref" as name was because of this video. youtube.com/… by Computerphile. And that is my bad as its more of a concept as compared to an actual triple ref pointer. \$\endgroup\$
    – Dagar
    Apr 28, 2021 at 2:34

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.