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.

Program List

1) Quicksort on doubly linked list in java 2) Quicksort on doubly linked list in c++ 3) Quicksort on doubly linked list in c 4) Quicksort on doubly linked list in golang 5) Quicksort on doubly linked list in c# 6) Quicksort on doubly linked list in vb.net 7) Quicksort on doubly linked list in php 8) Quicksort on doubly linked list in node js 9) Quicksort on doubly linked list in typescript 10) Quicksort on doubly linked list in python 11) Quicksort on doubly linked list in ruby 12) Quicksort on doubly linked list in scala 13) Quicksort on doubly linked list in swift 14) Quicksort on doubly linked list in kotlin

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.