# Quick Sort on SIngly Linked List

## 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 //
{
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

else //make the next of the current LLNode point to the present head and make the current LLNode as the new head
{
}

//O(1) constant time
}

// A utility function to print linked list //
{
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)

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)

// 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

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

// Change next of last LLNode of the left half to pivot
tmp->next =  pivot;
}

// Recur for the list after the pivot element
pivot->next = quickSortRecur(pivot->next, newEnd);

}

// The main function for quick sort. This is a wrapper over recursive
// function quickSortRecur()
{
return;
}

// Driver program to test above functions
int main()
{
LLNode *head = NULL;
LLNode *tail = NULL;

cout << "Linked List before sorting \n";