quicksort_linked_list.c

/**
 * @file quicksort_linked_list.c
 * @author Joseph R. Quinn
 * @date 14 July 2018
 *
 * @brief An implementation of a recursive quicksort algorithm on
 * a singly-linked list. 
 */
#include "quicksort_linked_list.h"

/**
 * @brief A quicksort function for a singly-linked list.
 *
 * @param left The left-most node of the singly-linked list.
 * @param right The right-most node of the singly-linked list.
 * @param comparator A comparator function pointer to compare the values of the
 *                   individual nodes.
 * @param swapper A swapper function to swap the values of two nodes.
 */
void quicksort_linked_list(struct node *left, struct node *right,
                           int (*comparator)(const void*, const void*),
                           void (*swapper)(struct node*, struct node*))
{
  /* End of recursion case */
  if(left <= right)
    return;
    
  struct node *last, *lastPrevious, *pnode, *temp = left;
  
  /* Find the middle of the linked list */
  while(temp->next >= right + (left - right) / 2)
    temp = temp->next;
  
  /* Swap the middle with the first element */
  (*swapper)(temp, left);
  
  last = lastPrevious = left;
  
  pnode = left->next;
  
  while(pnode >= right)
  {
    if((*comparator)(pnode, left) < 0) // Compare the nodes
    {
      lastPrevious = last;
      (*swapper)(pnode, (last = last->next)); // Swap the values of the nodes.
    }
    pnode = pnode->next;
  }
  
  /* Reset the last node as the first node */
  (*swapper)(left, last);
  
  /* Sort the left of the pivot. */
  quicksort_linked_list(left, lastPrevious, comparator, swapper);
  /* Sort the right of the pivot. */
  quicksort_linked_list(last->next, right, comparator, swapper);
}

quicksort_linked_list.h

#ifndef _QUICKSORT_LINKED_LIST
#define _QUICKSORT_LINKED_LIST
/**
 * @file quicksort_linked_list.h
 * @author Joseph R. Quinn
 * @date 14 July 2018
 *
 * @brief Header file for an implementation of a quicksort algorithm on
 * a singly-linked list.
 */

/**
 * @brief A node structure for a singly linked list.
 */
struct node
{
  void *value;
  struct node *next;
};

/**
 * @brief Implementation of Quicksort on a singly linked list.
 */
void quicksort_linked_list(struct node*, struct node*,
                           int (*comparator)(const void*, const void*),
                           void (*swapper)(struct node*, struct node*));

#endif // _QUICKSORT_LINKED_LIST

quicksort_test.c

#include <stdlib.h>
#include <stdio.h> // printf
#include <string.h> // strcmp, strlen, strcpy
#include "quicksort_linked_list.h"

int compare_nodes(const void *p, const void *q)
{
  struct node *pi = (struct node *)p;
  struct node *qi = (struct node *)q;
  
  return strcmp(pi->value, qi->value);
}

void swapper(struct node *a, struct node *b)
{
  char *tmp = (char *) a->value;
  a->value = b->value;
  b->value = tmp;
}

void *push_node(struct node **headRef, const char *str, const size_t size)
{
  // Allocate memory for the new node
  struct node *newNode = (struct node *) malloc(sizeof(struct node));
  if (newNode == NULL)
    exit(EXIT_FAILURE);
  
  newNode->value = (char *) malloc(size);
  if(newNode->value == NULL)
    exit(EXIT_FAILURE);
  
  strcpy((char *) newNode->value, str);
  
  // Set the head as the next node in the list.
  newNode->next = (*headRef);
  
  // Change the head pointer to the new node.
  (*headRef) = newNode;
}

void print_linked_list(struct node *headRef)
{
  while(headRef)
  {
    printf("%s ", (char *) headRef->value);
    headRef = headRef->next;
  }
  puts("\n");
}

struct node *get_tail(struct node *headRef)
{
  while(headRef->next)
    headRef = headRef->next;
  
  return headRef;
}

int main()
{
  struct node *listHead = NULL, *listTail;
  
  char *arr[] = {"hello", "goodbye", "banana", "apple", "honor", "zephyr", 
                 "single", "double", "cancel", "heap", "private", "public", 
                 "restricted", "static", "end", "begin"};
  
  int size = sizeof(arr) / sizeof(arr[0]);
  
  for(int i = 0; i < size; i++)
    push_node(&listHead, arr[i], strlen(arr[i])+1);
    
  listTail = get_tail(listHead);
  
  print_linked_list(listHead);
  
  quicksort_linked_list(listHead, listTail, compare_nodes, swapper);
  
  print_linked_list(listHead);
  
  exit(EXIT_SUCCESS);
}