insertion.c

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

struct node {
  struct node *next;
  struct node *prev; // Used if we assumble doubly linked list.
  int val;
};

void print_list(struct node *list) {
  struct node *ptr = list;

  printf("\n");
  while (ptr) {
    printf("<val: %d,\t", ptr->val);
    if (ptr->next)
      printf("next: %d,\t", ptr->next->val);
    else
      printf("next: null,\t");

    if (ptr->prev)
      printf("prev: %d>\n", ptr->prev->val);
    else
      printf("prev: null>\n");

    ptr = ptr->next;
  }
  printf("\n");
}

struct node *sort(struct node *list, int size) {

  // We want the smallest element at the beginning immediately, since this is a singly linked list.
  struct node *smallest = list;
  struct node *smallest_prev = NULL; // Represents the element behind the smallest.

  struct node *iterator_prev = list;
  struct node *iterator = list->next;

  while (iterator) {

    if (smallest->val > iterator->val) {
      smallest = iterator;
      smallest_prev = iterator_prev;
    }

    iterator_prev = iterator;
    iterator = iterator->next;
  }

  // Swap the elements.
  if (smallest_prev) {
    struct node *swap = list;
    struct node *smallest_next = smallest->next;

    list = smallest;
    list->next = swap->next;

    smallest = swap;
    smallest_prev->next = smallest;
    smallest->next = smallest_next;
  }

  // Now perform insertion sort assuming the beginning of the list is sorted.
  struct node *sorted = list;
  struct node *unsorted = list->next;
  
  while (unsorted) {
    struct node *iterator = sorted;
    while (iterator->next != unsorted) {

      // Found the right place to put the unsorted value.
      if (iterator->next->val > unsorted->val) {
        struct node *iterator_next = iterator->next;
        struct node *unsorted_next = unsorted->next;
        iterator->next = unsorted;
        unsorted->next = iterator_next;

        if (iterator_next->next == unsorted) {
          iterator_next->next = unsorted_next;
        }

        unsorted = unsorted_next;
        break;
      }

      iterator = iterator->next;
    }

    // The unsorted should be the last element.
    if (iterator->next == unsorted) {
      unsorted = unsorted->next;
    }
  }

  return sorted;
}

int main() {
  // Construct some nodes
  struct node node1, node2, node3, node4, node5;

  node1.next = &node2; node1.prev = NULL;
  node2.next = &node3; node2.prev = NULL;
  node3.next = &node4; node3.prev = NULL;
  node4.next = &node5; node4.prev = NULL;
  node5.next = NULL;   node5.prev = NULL;

  node1.val = 5;
  node2.val = 10;
  node3.val = 1;
  node4.val = 73;
  node5.val = 42;

  print_list(&node1);
  struct node * sorted_list = sort(&node1, 5);
  print_list(sorted_list);
  
  return 0;
}