CLOSE

Data Structures  Algorithm  Linked List  Quick Sort
Technology    Programming

# Use Quick Sort to Sort a Linear Linked List

AUGUST 22, 2019   by Yash3199

Quicksort algorithm is based on the concept of divide and conquer, where we do all the main work of sorting while dividing the given data structure(can be an array or in this case a Linked List) and during merging the data back, absolutely no processing is done, data is simply combined back together.

Quick Sort is also known as Partition-Exchange Sort.

In the quick sort algorithm, the given dataset is divided into three sections,

1. Data elements less than the pivot

2. The data element which is the pivot

3. And the data elements greater than the pivot.

Also in this case, when we want to use quicksort with a linked list, the main idea is to swap pointers(in the node) rather than swapping data.

## Steps of the Algorithm:

The whole algorithm can be divided into two parts,

### Partition:

1. Take the rightmost element as the pivot.

2. Traverse through the list:

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

2. else, keep it in the same position.

### Quick Sort:

1. Call the `partition()` method, which will place the pivot at the right position and will return the pivot

2. Find the tail node of the left sublist i.e., left side of the pivot and recur the whole algorithm for the left list.

3. Now, recur the algorithm for the right list.

## Implementation in C/C++:

As we have seen the algorithm, let's now move on to the actual 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 list is empty then set the current formed LLNode as head of list
}
else {
/*     make the next of the current LLNode point to the
*/
}
//  O(1) constant time
}

// A utility function to print linked list
{

// till the list ends (NULL marks ending of list)
while(temp!=NULL) {

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

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

// Update newEnd to the current last node
(*newEnd) = tail;

// Return the pivot LLNode
return pivot;
}

//  here the sorting happens exclusive of the end node
{
// base condition

LLNode *newHead = NULL, *newEnd = NULL;

/*    Partition the list, newHead and newEnd will be updated
by the partition function
*/

/*    If pivot is the smallest element - no need to recur for
the left part.
*/

// Set the LLNode before the pivot LLNode as NULL

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 *tail = NULL;

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

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

return 0;

}``````

## Time Complexity of the Algorithm

The worst case time complexity of this algorithm is `O(n^2)` and the average case complexity is `O(nlogn)`. 