# Perform quick sort in doubly linked list

This article addresses the implementation of the QuickSort algorithm on a doubly linked list. QuickSort is a popular sorting algorithm known for its efficiency and ease of implementation. This article will guide you through the process of performing QuickSort on a doubly linked list, along with explanations and code examples.

## Problem Statement

Given a doubly linked list, the goal is to sort its elements in non-decreasing order using the QuickSort algorithm.

## Example

Consider the following doubly linked list:

``4 <-> 3 <-> 7 <-> 1 <-> -1 <-> 6 <-> 2 <-> 8 <-> -2 <-> 0``

After applying QuickSort, the list should become:

``-2 <-> -1 <-> 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 6 <-> 7 <-> 8``

## Idea to Solve

QuickSort is a recursive sorting algorithm that works by selecting a pivot element and partitioning the array into two sub-arrays – elements less than the pivot and elements greater than the pivot. This process is repeated for the sub-arrays until the entire list is sorted.

## Pseudocode

``````function partition(first, last):
current = first
location = first.prev
temp = 0
while current is not null and current is not last:
if current.data <= last.data:
if location is null:
location = first
else:
move location to the next node
swap current.data and location.data
move current to the next node
if location is null:
location = first
else:
move location to the next node
swap last.data and location.data
return location

function quickSort(first, last):
if first is not last and first is not null and
last is not null and last.next is not first:
node = partition(first, last)
if node is not null:
quickSort(node.next, last)
quickSort(first, node.prev)``````

## Algorithm Explanation

1. Implement a partition function that takes two pointers, `first` and `last`, as parameters.
2. Initialize `current` to `first` and `location` to `first.prev`.
3. Traverse the linked list with the `current` pointer and swap nodes' data if necessary, keeping track of the `location` of the pivot.
4. After traversing, swap the data of the `last` node and the `location` node.
5. Return the `location` node as the new pivot.
6. Implement the `quickSort` function that recursively sorts the linked list:
• If the base conditions are met (i.e., valid pointers and non-empty sub-array), partition the list using the `partition` function and obtain the pivot node.
• Recursively apply `quickSort` to the sub-arrays before and after the pivot node.

## Time Complexity

The time complexity of QuickSort largely depends on the choice of the pivot. On average, the time complexity is O(n log n), which makes it one of the fastest sorting algorithms.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.