QuickSort on a Doubly Linked List

GAZAL ARORA
Last Updated: May 13, 2022

Question

Implement QuickSort on a Doubly Linked List.

If you're unfamiliar with QuickSort's Array Implementation, I recommend you to look at it before continuing with this post.


Alert Ninjas: Don't stop now! Enroll in the Competitive Programming course today and start coding. Learn the art of writing time and space-efficient code and compete in code competitions worldwide. 


For example,

Source

Linked List before sorting
15  12  8  4  2

Linked List after sorting
2  4  8  12  15

Solution


Recommended: Please try to solve it yourself first before moving on to the solution.


The idea is simple:

  • We will first find the pointer to the last node of the Linked List. 
  • We can recursively sort the Linked List using pointers to the first and last nodes of a linked list, similar to the recursive method where we pass indexes of first and last array elements. 
  • A linked list's partition function is similar to that of an array's partition function. It will return a pointer to the pivot element instead of the index of the pivot element.

Below is the C++ implementation of QuickSort on a Doubly Linked List:

// QuickSort on a Doubly Linked List

#include <bits/stdc++.h>
using namespace std;
// a node of a doubly linked list.
class Node
{
public:
    int data;
    Node *next;
     Node *prev;
};

/* A helper function to swap elements. */
void swap ( int* x, int* y ){ 
    
    int temp = *x; 
    *x = *y; 
    *y = temp; 
}

// A helper function to find the last node of the linked list.
Node *lastNode(Node *head)
{
    Node *root = head;
while (root && root->next)
root = root->next;
return root;
}

//Consider the last element as pivot.
Node* partition(Node *start, Node *end)
{
// set pivot as end element.
int pivot = end->data;

// similar to i = l-1 for array implementation.
Node *i = start->prev;

for (Node *temp = start; temp != end; temp = temp->next)
{
if (temp->data <= pivot)
{
    
            if( i == NULL)
                i = start; 
            else
                i = i->next;

            swap(&(i->data), &(temp->data));
}
}

if( i == NULL)
                i = start;
    else
                i = i->next;
                
swap(&(i->data), &(end->data));
return i;
}

// implementation of quicksort.
void _quickSort(Node *start, Node *end)
{
if (end != NULL && start != end && start != end->next)
{
Node *pivot = partition(start, end);
_quickSort(start, pivot->prev);
_quickSort(pivot->next, end);
}
}

void quickSort(Node *root)
{
    
Node *end = lastNode(root);
Node *head = root;
_quickSort(head, end); 
}

// A helper function to print contents of arr.
void printList(Node *root)
{
while (root)
{
cout << root->data << " ";
root = root->next;
}
cout << endl;
}

//helper function to insert a node in the beginning. 
void push(Node** head, int data)
{
Node* node = new Node;
node->data = data;

node->prev = NULL;
node->next = (*head);

if ((*head) != NULL) 
    (*head)->prev = node ;


(*head) = node;
}

/* Driver code */
int main()
{
Node *root = NULL;
push(&root, 2);
push(&root, 4);
push(&root, 8);
push(&root, 12);
push(&root, 15);

cout << "Linked List before sorting \n";
printList(root);

quickSort(root);

cout << "Linked List after sorting \n";
printList(root);
return 0;
}

Output

Time Complexity

The above implementation is the same as QuickSort for arrays. Therefore time complexity is also the same as that of the time complexity of QuickSort for an array.

In the worst case, it takes O(n2) time, whereas, in the average and best cases, it takes O(NLogN). When the linked list is already sorted, the worst case occurs.

Key takeaways

Here we saw how to implement QuickSort on a Doubly Linked List. Join this Master Class on DP by Coding Ninjas and become a Ninja coder.

Challenge: Can you implement random QuickSort for a linked list? 
Random QuickSort is when we choose pivot randomly. We can only implement Quicksort for Linked List when we can choose a fixed point as the pivot (like the last element in the above implementation). Therefore, Random QuickSort cannot be implemented for Linked Lists.

Start coding today, practice more Data Structures and Algorithms problems. 
Happy Coding!

Was this article helpful ?
0 upvotes