## Given a linked list, we will sort the linked list using quick sort.

### Example

**Linked List before sorting**

23 ->1 ->50 ->15 ->16 ->6

**Linked List after sorting**

1 ->6 ->15 ->16 ->23 ->50

**Time Complexity : O()**

In this method the main idea is to swap pointers rather than swaping data

## Algorithm

### Partition Algorithm

**1.** Take rightmost element as the pivot

Traverse through the list

** a.** If the node has value greater than pivot, we will move it after tail

** b.** else, keep it in same position

### QuickSort Algorithm

**1.** Call Partition(), which places pivot at right position and returns the pivot

**2. ** Find the tail node of the left sublist ie, left side of the pivot and recur for left list

**3.** Now, recur for right list

## C++ Program

```
#include <iostream>
#include <cstdio>
using namespace std;
// a node of the singly linked list //
struct LLNode
{
int data;
LLNode *next;
};
//utility function to insert a LLNode at the beginning of linked list //
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
LLNode*curr=new LLNode;
//make a new LLNode with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next=NULL;
if(*head==NULL) //if list is empty then set the current formed LLNode as head of list
*head=curr;
else //make the next of the current LLNode point to the present head and make the current LLNode as the new head
{
curr->next=*head;
*head=curr;
}
//O(1) constant time
}
// A utility function to print linked list //
void display(LLNode**head)
{
LLNode*temp=*head;
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;
temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}
// Returns the last node of the list
LLNode *getTail(LLNode *cur)
{
while (cur != NULL && cur->next != NULL)
cur = cur->next;
return cur;
}
// Partitions the list taking the last element as the pivot
LLNode *partition(LLNode *head, LLNode *end, LLNode **newHead, LLNode **newEnd)
{
LLNode *pivot = end;
LLNode *prev = NULL, *cur = head, *tail = pivot;
// During partition, both the head and end of the list might change
// which is updated in the newHead and newEnd variables
while (cur != pivot)
{
if (cur->data < pivot->data)
{
// First node that has a value less than the pivot - becomes
// the new head
if ((*newHead) == NULL)
(*newHead) = cur;
prev = cur;
cur = cur->next;
}
else // If cur LLNode is greater than pivot
{
// Move cur LLNode to next of tail, and change tail
if (prev)
prev->next = cur->next;
LLNode *tmp = cur->next;
cur->next = NULL;
tail->next = cur;
tail = cur;
cur = tmp;
}
}
// If the pivot data is the smallest element in the current list,
// pivot becomes the head
if ((*newHead) == NULL)
(*newHead) = pivot;
// Update newEnd to the current last node
(*newEnd) = tail;
// Return the pivot LLNode
return pivot;
}
//here the sorting happens exclusive of the end node
LLNode *quickSortRecur(LLNode *head, LLNode *end)
{
// base condition
if (!head || head == end)
return head;
LLNode *newHead = NULL, *newEnd = NULL;
// Partition the list, newHead and newEnd will be updated
// by the partition function
LLNode *pivot = partition(head, end, &newHead, &newEnd);
// If pivot is the smallest element - no need to recur for
// the left part.
if (newHead != pivot)
{
// Set the LLNode before the pivot LLNode as NULL
LLNode *tmp = newHead;
while (tmp->next != pivot)
tmp = tmp->next;
tmp->next = NULL;
// Recur for the list before pivot
newHead = quickSortRecur(newHead, tmp);
// Change next of last LLNode of the left half to pivot
tmp = getTail(newHead);
tmp->next = pivot;
}
// Recur for the list after the pivot element
pivot->next = quickSortRecur(pivot->next, newEnd);
return newHead;
}
// The main function for quick sort. This is a wrapper over recursive
// function quickSortRecur()
void quickSort(LLNode **headRef)
{
(*headRef) = quickSortRecur(*headRef, getTail(*headRef));
return;
}
// Driver program to test above functions
int main()
{
LLNode *head = NULL;
LLNode *tail = NULL;
insertAtBeginning(&head, 6);
insertAtBeginning(&head, 16);
insertAtBeginning(&head, 15);
insertAtBeginning(&head, 50);
insertAtBeginning(&head, 1);
insertAtBeginning(&head, 23);
cout << "Linked List before sorting \n";
display(&head);
quickSort(&head);
cout << "Linked List after sorting \n";
display(&head);
return 0;
}
```