1
\$\begingroup\$

I am trying to implement binary radix sort in C which sorts a linked list of integers stably. Although my algorithm has a time complexity of O(log2(k).n) (where k is the biggest integer in the linked list), other standard implementations of algorithms like merge sort/quick sort seem to have better execution time even when input size is large (n>10^6) and kis small (k<1000). Am I doing something wrong which is causing these longer execution times? Could you review this code?

Here is the code for my implementation:

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
struct ListNode {
     int val;
     struct ListNode *next;
};
void print_list(struct ListNode *node) // printing integer values of linked list
{
  while(node!=NULL)
  {
    printf("%d, ", node->val);
    node=node->next;
  }
}
int getMax(struct ListNode *node) // finding biggest integer in linked list
{
  int max=node->val;
  while(node!=NULL)
  {
    if(node->val > max)
    {
      max=node->val;
    }
    node=node->next;
  }
  return max;
}
void addMin(struct ListNode *node, int min) // Adding smallest integer in linked list so that no integer in linked list is negative
{
  while(node!=NULL)
  {
    node->val+=min;
    node=node->next;
  }
}
void subMin(struct ListNode *node, int min) // returning linked list to original values after sorting
{
  while(node!=NULL)
  {
    node->val-=min;
    node=node->next;
  }
}
int getMin(struct ListNode *node) // finding smallest integer in linked list
{
  int min=node->val;
  while(node!=NULL)
  {
    if(node->val < min)
    {
      min=node->val;
    }
    node=node->next;
  }
  return min;
}
void binarySort(struct ListNode **head, int bit) // sorts linked list based on a particular bit
{
  struct ListNode *temp = *head;
  struct ListNode *insertNode = *head;
  struct ListNode *prevNode = NULL;
  int flag=0;
  int flag2=0;
  if((((*head)->val) & (1 << (bit - 1))))
  {
    flag=1;
  }
  while(temp!=NULL)
  {
    if(flag==0 && !((temp->val) & (1 << (bit - 1))))
    {
      if((temp->next)!=NULL && (((temp->next)->val) & (1 << (bit - 1))))
      {
        insertNode=temp;
        flag=1;
        flag2=1;
      }
    }
    else if(flag2==0 && !((temp->val) & (1 << (bit - 1))))
    {
      prevNode->next=temp->next;
      temp->next=*head;
      insertNode=temp;
      *head=temp;
      temp=prevNode;
      flag=1;
      flag2=1;
    }
    else if(!((temp->val) & (1 << (bit - 1))))
    {
      prevNode->next=temp->next;
      temp->next=insertNode->next;
      insertNode->next=temp;
      insertNode=temp;
      temp=prevNode;
    }
    prevNode=temp;
    temp=temp->next;
  }
}
struct ListNode* sortList(struct ListNode* head) // binary radix sort
{
  if(head==NULL)
  {
    return NULL;
  }
  int min=getMin(head);
  if(min<0)
  {
    subMin(head, min);
  }
  int biggest_int_len = log2(getMax(head))+1;
  int i;
  for(i=1 ; i<=biggest_int_len ; i++)
  {
    binarySort(&head, i);
  }
  if(min<0)
  {
    addMin(head, min);
  }
  return head;
}
int main() // code to test the function
{
  srand(time(0));
  int num;
  struct ListNode *head = (struct ListNode*) malloc(sizeof(struct ListNode));
  head->next=NULL;
  printf("Enter input size: ");
  scanf("%d", &num);
  head->val=rand()%1000;
  struct ListNode *prevNode = head;
  while(num-1>0)
  {
    struct ListNode *temp = (struct ListNode*) malloc(sizeof(struct ListNode));
    temp->val=rand()%1000;
    temp->next=NULL;
    prevNode->next=temp;
    prevNode=temp;
    num--;
  }
  printf("\n\n");
  print_list(head);
  clock_t t;
  t = clock();
  struct ListNode *sortedList=sortList(head);
  t = clock() - t;
  double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
  printf("\n\n");
  print_list(sortedList);
  printf("\n\nfun() took %f seconds to execute \n", time_taken);
}

Also is there a good way to test how much memory the sort uses?

\$\endgroup\$
2
  • \$\begingroup\$ To handle negative numbers, just add special logic for sign bits (reverse it) may save findMin, subMin, addMin parses. Also, you may avoid find max value first, but know if I'm running last parse in binarySort. In binarySort, maintain 2 linked list and concat them when all values add to some of them would simplify your codes. \$\endgroup\$ – tsh Feb 1 at 6:31
  • \$\begingroup\$ Thank you for your suggestions. I will try to implement them. \$\endgroup\$ – Mathphile Feb 1 at 20:39
1
\$\begingroup\$
  • Performance

    The root cause is a poor referential locality. As sorting progresses, and the nodes get relinked, they become accessed in no particular order, all over the memory. This results in too many cache misses, and a cache miss is very expensive.

  • binarySort is a bit too complicated. It is very hard to follow. Things like flag, and flag2, (what do they signify?) are always a signal of an unclear design.

    It seems that those flags stem from the special-casing a head node. Try to avoid special cases. Usually having a dummy node greatly simplifies the design. Consider (untested)

      void binarySort(struct ListNode ** head, int bit)
      {
          struct ListNode dummy = { .next = *head };
          struct ListNode *base = &dummy;
          struct ListNode *prev = base;
          struct ListNode *curr = prev->next;
          while (curr != NULL) {
              if (!bit_is_set(curr->val, bit)) {
                  prev->next = curr->next;
                  curr->next = base->next;
                  base = curr;
              } else {
                  prev = prev->next;
              }
              curr = prev->next;
          }
          *head = dummy.next;
      }
    
\$\endgroup\$
3
  • \$\begingroup\$ Had you ever changed curr in the loop? And maybe the condition curr != NULL will never change and the loop will never finish. \$\endgroup\$ – tsh Feb 2 at 3:24
  • \$\begingroup\$ Typo. Thanks, The cursor shall be curr. Fixed. \$\endgroup\$ – vnp Feb 2 at 7:26
  • \$\begingroup\$ Ah your code seems to make much more sense. Thank you for the answer. \$\endgroup\$ – Mathphile Feb 2 at 12:16

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.