QuickSortLinkLists

//Quick sort on Link Lists

//Doubly LinkList

//Note:- tricky check while swap

#include<iostream>

using namespace std;

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

struct List
{
   int data;
   List* next;
   List* prev;
};

void Insert(Node** head, int data)
{
   if(*head == NULL)
   {
      *head = new Node();
      (*head)->data = data;
      (*head)->next = NULL;
   }
   else
   {
      Insert(&((*head)->next),data);
   }
}


void ListInsert(List** head, int data,List* prev)
{
   if(*head == NULL)
   {
      *head = new List();
      (*head)->data = data;
      (*head)->next = NULL;
      (*head)->prev = prev;
   }
   else
   {
      prev = *head;
      ListInsert(&((*head)->next),data,prev);
   }
}

void PrintList(List* head)
{
    cout<<endl;
    while(head)
    {
        cout<<head->data<<"  ";
        head = head->next;
    }
    cout<<endl;

}

void PrintLinkList(Node* head)
{
    cout<<endl;
    while(head)
    {
        cout<<head->data<<"  ";
        head = head->next;
    }
    cout<<endl;
}

void swap(int &i, int &j)
{
   int temp = i;
   i = j;
   j = temp;
}

List* partition(List* low,List* high)
{
   
   int pivot = high->data;

   List *end = high;

   high = high->prev;

   while(low != high)
   {
       if(low->data <= pivot)
       {
            low = low->next;
       }
       else if(high->data > pivot)
       {
            high = high->prev;
       }
       else
       {
           swap(low->data,high->data);  
       }
   }

 

   if(low->data == pivot)
   {
     
      return low;
   }
   else if(low->data > pivot)
   {
     
      swap(low->data,end->data);
      return low;
   }
   else
   {
      List *t = low->next;
      swap(t->data,end->data);
      return t;
   }
}

void q_sort_list_util(List* low,List* high)
{
  if(low != high)
  {
     List* p = partition(low,high);
     if(p != low)
     q_sort_list_util(low,p->prev);
     if(p != high)
     q_sort_list_util(p->next,high);
     
  }
 
}

void q_sort_list(List* head)
{
   List* high = head;

  while(high->next != NULL) high = high->next;

  q_sort_list_util(head,high);

}
int main()
{

   List* head1 = NULL;

  ListInsert(&head1,10,NULL);
  ListInsert(&head1,9,NULL);
  ListInsert(&head1,8,NULL);
  ListInsert(&head1,7,NULL);
  ListInsert(&head1,5,NULL);
  ListInsert(&head1,4,NULL);
  ListInsert(&head1,2,NULL);

  

   q_sort_list(head1);

   PrintList(head1);

   Node* head2 = NULL;

  Insert(&head2,2);
  Insert(&head2,4);
  Insert(&head2,6);
  Insert(&head2,8);
  Insert(&head2,10);
  Insert(&head2,11);
  Insert(&head2,12);
 
  return 0;
}