Quicksort data structures are a way of sorting a list of items. This uses a divide and conquer approach. That is, the array of elements is divided into two parts and a quick sort algorithm is applied to these two parts. This matrix division is done using pivot points. The position of the pivot is chosen so that the element on the left side of the pivot is smaller than the pivot element and the element on the right side is larger than the pivot element. This partition is meant to get a linear run-time ordered array.

In C ++ implementation of a double-linked list. The idea is simple. First, find the pointer to the last node. Once you have a pointer to the last node, you can recursively sort the linked list using the pointers to the first and last node of the linked list. This is similar to the recursive function above, which passes the indices of the first and last element of the array. The linked list partition function is also similar to an array partition. Instead of returning the index of the pivot element, it returns a pointer to the pivot element. In the following implementation, quickSort () is just a wrapper function and the main recursive function is _quickSort (), similar to the quickSort () array implementation.

**For example:**

**Here Code:**

#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node *next; Node *prev; }; void swap ( int* a, int* b ) { int t = *a; *a = *b; *b = t; } Node *lastNode(Node *root) { while (root && root->next) root = root->next; return root; } Node* partition(Node *l, Node *h) { int x = h->data; Node *i = l->prev; for (Node *j = l; j != h; j = j->next) { if (j->data <= x) { i = (i == NULL)? l : i->next; swap(&(i->data), &(j->data)); } } i = (i == NULL)? l : i->next; swap(&(i->data), &(h->data)); return i; } void _quickSort(Node* l, Node *h) { if (h != NULL && l != h && l != h->next) { Node *p = partition(l, h); _quickSort(l, p->prev); _quickSort(p->next, h); } } void quickSort(Node *head) { Node *h = lastNode(head); _quickSort(head, h); } void printList(Node *head) { while (head) { cout << head->data << " "; head = head->next; } cout << endl; } void push(Node** head_ref, int new_data) { Node* new_node = new Node; new_node->data = new_data; new_node->prev = NULL; new_node->next = (*head_ref); if ((*head_ref) != NULL) (*head_ref)->prev = new_node ; (*head_ref) = new_node; } int main() { Node *a = NULL; push(&a, 10); push(&a, 2); push(&a, -1); push(&a, 9); push(&a, 5); cout << "Linked List before sorting \n"; printList(a); quickSort(a); cout << "Linked List after sorting \n"; printList(a); return 0; }

**Complexity Analysis:**

**Time Complexity**: Time complexity is O (n ^ 2) hours at worst, average, and O (nLogn) at best.

**Conclusion:**

The quick sort method uses the divide and conquer method to sort the items. It supports in-place caching and is also a queuing recursive algorithm. This is most preferred because arrays require a lot of access to items and linked lists take a long time.

**Recommended Articles:**

- Insertion in Doubly Linked List
- Deletion in Doubly Linked List
- How to reverse a doubly linked list?
- Merge Sort for Doubly Linked List
- How to reverse a string using stack?

**References:**

- https://tutorialspoint.dev/algorithm/sorting-algorithms/quicksort-for-linked-list
- https://www.studytonight.com/post/use-quick-sort-to-sort-a-doubly-linked-list
- https://www.javatpoint.com/program-to-sort-the-elements-of-the-doubly-linked-list

[…] QuickSort on Doubly Linked List […]