QuickSort on a Doubly Linked List
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.
Linked List before sorting
15 12 8 4 2
Linked List after sorting
2 4 8 12 15
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
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.
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.