#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct Node Node;
 
 
struct Node
{
  void* info; //data
  Node* next; //used to point to next node
};
 
 
//this implementation doesn't use any explicit special header node
//one has to maintain a start point of a list to track all other nodes
//so createlist is a dummy one
Node *createlist()
{
  return NULL;
}
 
//insert after a known node and return the node before inserted node
Node *insert(Node *after, long* data)
{
  Node* n;
  n = malloc (sizeof(Node));
  n->info = data;
 
  //incase header node is not created
  if (!after)
  {
    n->next = after;
    return n;
  }
 
  n->next = after->next;
  after->next = n;
 
  return after;
}
 
void destroylist(Node **n)
{
  Node * tmp;
 
  if (!n || !*n)
  {
    return;
  }
 
  while(*n)
  {
    tmp = (*n)->next;  
    free(*n);
    *n = tmp;
  }
}
 
 
//given a node in list, prints entire list after the node
int printlist(Node *h)
{
  Node* t = h;
 
  while(t)
  {
    printf(" %d ->", *(long*)t->info);
    t = t->next;
  }
 
  printf(" NULL\n");
  return 0;
}
 
 
//find previous node of curr node
Node *FindPrev(Node *list, Node *curr)
{
  for(;list && list->next; list=list->next)
  {
    if(curr == list->next)
    {
      break;
    }
  }
 
  if (list->next != curr)
  {
    //not find any element, probably what we are 
    //searching for is the beginning node
    return curr;
  }
 
  return list;
}
 
/*A complete swap algorithm which cares of 
several scenarios while swapping two nodes in 
a linked list which doesn't have any special nodes
scenarios considered while swapping
1)two nodes which are far away
2)two nodes which are far away, one is node is at 
  beginning of the list
3)two node which are neighbors
4)two nodes which are neibhors, 
  one node is at beginning of the list
*/
Node *SwapNodes(Node *list, Node *node1, Node *node2)
{
 
  Node *node1prev, *node2prev, *tmp;
 
  node1prev = FindPrev(list, node1);
  node2prev = FindPrev(list, node2);
 
  tmp = node2->next;
 
  //check whether node to swapped is in 
  //beggining (i.e. header node)
  if (node1 != list)
  {
    node1prev->next = node2;
  }
  else
  {
    //as we do not have special header node, 
    //if the first node and some 
    //other node, need to be swapped, 
    //then update the list (makes new min node as 
    //logical header)
    list = node2;
  }
 
  //are nodes to be swapped neibgoring nodes?
  if (node1->next == node2)
  {
    //nodes to be swapped are neibhoring nodes,
    //then swap them simply
    node2->next = node1;
    node1->next = tmp;
  }
  else
  {
    //nodes to be swapped are not neibhor nodes, 
    //they are apart
    //so, consider all scenarios
    node2->next = node1->next;
 
    node1->next = tmp;
    node2prev->next = node1;
  }
  return list;
}
 
/*an auxilory routine for getting the Nth 
element in the linked list*/
Node *GetNthNode(Node *list, int n)
{
  int i=1;
  for(i=1;i<n;i++)
  {
    list = list->next;
  }
  return list;
}
 
/*count number of nodes between two nodes 
(including the start, end mentioned)*/
int NumNodes(Node *list, Node *end)
{
  int i;
 
  for(i=1;list && (list!=end);i++)
  {
    list = list->next;
  }
 
  if (list != end)
  {
    return 0;
  }
  return i;
}
 
//total nodes in list
int countnodes(Node *list)
{
  int i = 0;
 
  for (;list; list=list->next)
  {
    i++;
  }
 
  return i;
}
 
/*select a pivot, pivot can be selected in any way
randomly, first element, median of left, center, right
elemnts, etc.
Here we have chosen to pick center element as pivot*/
Node *SelectPivot(Node *list, Node *end)
{
  Node *right, *noden;
  int n;
 
  n=NumNodes(list, end);
 
  noden = GetNthNode(list, (int)((float)n/2+0.5));
  //
  right = FindPrev(list, end);
 
  if (noden != right)
  {
    //swap the pivot and right most element in the list
    //later pivot will be restored.
    SwapNodes(list, noden, right->next);
    return noden;
  }
  else
  {
    return noden->next;
  }
}
 
/*the actual quciksort routine*/
Node * quicksort(Node *list, int list_start, int list_end) 
{
  Node *pivot, *left=list, *right=list, *tmp;
  int i = list_start, j= list_end-1;
 
  if (list_start >= list_end)
  {
    return list;
  }
 
  right = GetNthNode(list, list_end);
  left = GetNthNode(list, list_start);
 
  //select pivot
  pivot = SelectPivot(left, right);
 
  right = FindPrev(left, pivot);
 
  for(;;)
  {
    //now starts partitioning the list
    for(;*(long*)left->info < *(long*)pivot->info; left=left->next,i++);
 
    for(;*(long*)right->info > *(long*)pivot->info; right = FindPrev(list,right),j--);
    if (i < j)
    {
      list = SwapNodes(list, left, right);
      tmp = left;
      left = right;
      right = tmp;
    }
    else
      break;
  }
 
  //restore pivot
  list = SwapNodes(list, left, pivot); 
 
  //now sort on smaller linked lists
  list = quicksort(list, list_start, i-1);
  list = quicksort(list, i+1, list_end);
 
  return list;
}
 
//a wrapper for quicksort
Node *QSort(Node *list)
{
  int n;
 
  n=countnodes(list);
 
  //call the quick sort routine
  //we always number elements in linked list as
  //1,2..n instead of 0, 1.. n-1
  return quicksort(list, 1, n);
}
 
#define TEST
#ifdef TEST
 
int main()
{
  int i;
  Node *list2 = NULL;
  long data[] = {8,0,7,2,5,3,6,9,4,1};  
  //list2
  for(i = 0; i < sizeof(data)/sizeof(data[0]); i++)
    list2 = insert(list2, &data[i]);
 
  printf("unsorted linked list:\n");
  printlist(list2);
 
  printf("sorted linked list:\n");
  list2 = QSort(list2);
  printlist(list2);
 
  destroylist(&list2);
}
 
#endif