QuickSort on Doubly Linked List

Before moving forward with this article, I would recommend having a look at QuickSort’s Array Implementation first, if you aren’t familiar with it.

Let’s quickly recall the steps involved in Quicksort Algorithm.

1. The first step is to choose a pivot element from the input elements. (There are different ways for choosing pivot like leftmost element, rightmost element, random element, etc.)
2. The next step is to put this pivot element to its sorted position and this is achieved by arranging all the elements smaller or equal to pivot on its left and rest on its right. This step is called partitioning.
3. After partitioning, return the index of the pivot element.
4. Now divide the array/list into two parts from the pivot index and recursively repeat the above steps until the array/list cannot be divided further and thus resulting into a sorted list.

Now, let’s look at each step in detail with respect to doubly linked list.

Choosing Pivot Element

Implementation-wise, it is easy to choose the leftmost or rightmost element as a pivot because anyway we will be receiving a pointer to the leftmost and rightmost node as the input parameters to our partition function i.e. PARTITION(node left, node right). Also, for any other element as a pivot, we have to traverse to that element index unlike in arrays. But this shouldn’t be our concern as the time complexity of the partition function will remain $O(n)$ because we have to iterate over all the elements from left to right to arrange them as mentioned in step 2. So a better way is to go for a random pivot element with every call to partition and returning two pivot indices p1 and p2 by partitioning List into three parts as shown below.

As a result, we can avoid partition calls to already sorted elements between pivots p1 and p2 by using PARTITION(left, p1.prev) and PARTITION(p2.next, right) in QuickSort. Also, this way we can eliminate the possibility of worst-case scenarios in terms of time complexity including already sorted elements and all equal elements in the list. However for simplicity purposes, we will take the rightmost element as pivot i.e. node pivot = right.

Arranging Elements in Partition

At this stage, we have chosen pivot as the current rightmost element. Now we initialize a pointer i to outside our sub-list that is at the previous of left (i = left.prev) and while traversing the list from left to right, we will make sure that the elements before i are less or equal to pivot and after i are greater than pivot by following the code below,

for (node j = left; j != right; j = j.next)
{
    if (j.data <= pivot.data)
    {
        i = i.next;
        swap(i.data, j.data);
    }
}

After arranging elements, we swap i.data with pivot.data so that the pivot gets to its sorted position and then returns pointer i.

Pseudo-code for partition in QuickSort

node PARTITION(node left, node right)
{ // Select pivot
    node pivot = right;
    // Select i pointer
    node i = left.prev;
    // Arranging the elements
    for (node j = left; j != right; j = j.next)
    {
        if (j.data <= pivot.data)
        {
            i = i.next;
            swap(i.data, j.data);
        }
    }
    swap(i.data, pivot.data);
    return i;
}

QuickSort

In QuickSort, we use the pointer returned by the PARTITION function to divide the list further into two parts until the right pointer has not crossed the boundary of the doubly linked list and the left pointer has not crossed the right one i.e. if(right != null && left != right && left != right.next).

Pseudocode for QuickSort

void QuickSort(node left, node right)
{
    if (right != null && left != right && left != right.next)
    {
        node p = PARTITION(left, right);
        QuickSort(left, p.prev);
        QuickSort(p.next, right);
    }
}

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int val;
    struct Node *next;
    struct Node *prev;
};

struct Node *partition(struct Node *left, struct Node *right)
{
    struct Node *pivot = right;
    struct Node *i = left->prev;
    for (struct Node *ptr = left; ptr != right; ptr = ptr->next)
    {
        if (ptr->val <= pivot->val)
        {
            i = (i == NULL ? left : i->next);
            int temp = i->val;
            i->val = ptr->val;
            ptr->val = temp;
        }
    }
    i = (i == NULL ? left : i->next);
    int temp = i->val;
    i->val = pivot->val;
    pivot->val = temp;
    return i;
}
void QuickSort(struct Node *left, struct Node *right)
{
    if (right != NULL && left != right && left != right->next)
    {
        struct Node *p = partition(left, right);
        QuickSort(left, p->prev);
        QuickSort(p->next, right);
    }
}

int main()
{
    struct Node *head = malloc(sizeof(struct Node));
    head->val = 2;
    head->prev = NULL;
    struct Node *l1 = malloc(sizeof(struct Node));
    l1->val = 8;
    l1->prev = head;
    head->next = l1;
    struct Node *l2 = malloc(sizeof(struct Node));
    l2->val = 3;
    l2->prev = l1;
    l1->next = l2;
    struct Node *l3 = malloc(sizeof(struct Node));
    l3->val = 5;
    l3->prev = l2;
    l2->next = l3;
    struct Node *l4 = malloc(sizeof(struct Node));
    l4->val = 10;
    l4->prev = l3;
    l3->next = l4;
    l4->next = NULL;
    // 2<=>8<=>3<=>5<=>10=>NULL

    QuickSort(head, l4);
    while (head != NULL)
    {
        printf("%d ", head->val);
        head = head->next;
    }
    return 0;
}

class Node{
    int val;
    Node next;
    Node prev;
    Node(int val)
    {
        this.val = val;
    }
    Node(int val, Node prev)
    {
        this.val = val;
        this.prev = prev;
    }
}
public class MyClass {
    public static void main(String args[]) {
        Node head,first,second,third,fourth,fifth;
        head = new Node(6);
        head.next = first = new Node(2, head);
        first.next = second = new Node(1,first);
        second.next = third = new Node(7,second);
        third.next = fourth = new Node(9,third);
        fourth.next = fifth = new Node(3,fourth);
        // 6<=>2<=>1<=>7<=>9<=>3
        QuickSort(head,fifth);
        // Print the list.
        while(head!=null)
        {
            System.out.print(head.val+" ");
            head = head.next;
        }
    }
    public static Node partition(Node left, Node right)
    {
        Node pivot = right;
        Node i = left.prev;
        for(Node ptr=left; ptr!=right; ptr=ptr.next)
        {
            if(ptr.val<=pivot.val){
                i = (i==null?left:i.next);
                int temp = i.val;
                i.val = ptr.val;
                ptr.val = temp;
            }
        }
        i = (i==null?left:i.next);
        int temp = i.val;
        i.val = pivot.val;
        pivot.val = temp;
        return i;
    }
    public static void QuickSort(Node left, Node right)
    {
        if(right!=null && left!=right && left!=right.next)
        {
            Node p = partition(left,right);
            QuickSort(left,p.prev);
            QuickSort(p.next,right);
        }
    }
}

class Node:
    def __init__(self, val, prev=None):
        self.val = val
        self.next = None
        self.prev = prev


def partition(left, right):
    pivot = right
    i = left.prev
    ptr = left
    while ptr != right:
        if ptr.val <= pivot.val:
            i = left if i == None else i.next
            i.val, ptr.val = ptr.val, i.val
        ptr = ptr.next
    i = left if i == None else i.next
    i.val, pivot.val = pivot.val, i.val
    return i


def QuickSort(left, right):
    if right != None and left != right and left != right.next:
        p = partition(left, right)
        QuickSort(left, p.prev)
        QuickSort(p.next, right)


if __name__ == ("__main__"):
    head = Node(6)
    head.next = first = Node(2, head)
    first.next = second = Node(1, first)
    second.next = third = Node(7, second)
    third.next = fourth = Node(9, third)
    fourth.next = fifth = Node(3, fourth)
    # 6<=>2<=>1<=>7<=>9<=>3
    QuickSort(head, fifth)
    # Print the list.
    while head != None:
        print(head.val, end=" ")
        head = head.next