QuickSort on Singly Linked List

Last Updated : 10 Jan, 2023

Given a linked list, apply the Quick sort algorithm to sort the linked list. The important things about implementation are, that it changes pointers rather than swapping data.

Example:

sorting image

Follow the given steps to solve the problem:

Call partition function to get a pivot node placed at its correct position
- In the partition function, the last element is considered a pivot
- Then traverse the current list and if a node has a value greater than the pivot, then move it after the tail. If the node has a smaller value, then keep it at its current position.
- Return pivot node
Find the tail node of the list which is on the left side of the pivot and recur for the left list
Similarly, after the left side, recur for the list on the right side of the pivot
Now return the head of the linked list after joining the left and the right list, as the whole linked list is now sorted

Below is the implementation of the above approach:

C

#include <stdio.h> 
#include <stdlib.h> 
  
// Creating  structure 
struct Node { 
    int data; 
    struct Node* next; 
}; 
  
// Add new node at end of linked list 
void insert(struct Node** head, int value) 
{ 
    // Create dynamic node 
    struct Node* node 
        = (struct Node*)malloc(sizeof(struct Node)); 
    if (node == NULL) { 
        // checking memory overflow 
        printf("Memory overflow\n"); 
    } 
    else { 
        node->data = value; 
        node->next = NULL; 
        if (*head == NULL) { 
            *head = node; 
        } 
        else { 
            struct Node* temp = *head; 
  
            // finding last node 
            while (temp->next != NULL) { 
                temp = temp->next; 
            } 
  
            // adding node at last position 
            temp->next = node; 
        } 
    } 
} 
  
// Displaying linked list element 
void display(struct Node* head) 
{ 
    if (head == NULL) { 
        printf("Empty linked list"); 
        return; 
    } 
    struct Node* temp = head; 
    printf("\n Linked List :"); 
    while (temp != NULL) { 
        printf("  %d", temp->data); 
        temp = temp->next; 
    } 
} 
  
// Finding last node of linked list 
struct Node* last_node(struct Node* head) 
{ 
    struct Node* temp = head; 
    while (temp != NULL && temp->next != NULL) { 
        temp = temp->next; 
    } 
    return temp; 
} 
  
// We are Setting the given last node position to its proper 
// position 
struct Node* partition(struct Node* first, struct Node* last) 
{ 
    // Get first node of given linked list 
    struct Node* pivot = first; 
    struct Node* front = first; 
    int temp = 0; 
    while (front != NULL && front != last) { 
        if (front->data < last->data) { 
            pivot = first; 
  
            // Swapping  node values 
            temp = first->data; 
            first->data = front->data; 
            front->data = temp; 
  
            // Visiting the next node 
            first = first->next; 
        } 
  
        // Visiting the next node 
        front = front->next; 
    } 
  
    // Change last node value to current node 
    temp = first->data; 
    first->data = last->data; 
    last->data = temp; 
    return pivot; 
} 
  
// Performing quick sort in  the given linked list 
void quick_sort(struct Node* first, struct Node* last) 
{ 
    if (first == last) { 
        return; 
    } 
    struct Node* pivot = partition(first, last); 
  
    if (pivot != NULL && pivot->next != NULL) { 
        quick_sort(pivot->next, last); 
    } 
  
    if (pivot != NULL && first != pivot) { 
        quick_sort(first, pivot); 
    } 
} 
  
// Driver's code 
int main() 
{ 
    struct Node* head = NULL; 
  
    // Create linked list 
    insert(&head, 41); 
    insert(&head, 5); 
    insert(&head, 7); 
    insert(&head, 22); 
    insert(&head, 28); 
    insert(&head, 63); 
    insert(&head, 4); 
    insert(&head, 8); 
    insert(&head, 2); 
    insert(&head, 11); 
    printf("\n Before Sort "); 
    display(head); 
  
    // Function call 
    quick_sort(head, last_node(head)); 
    printf("\n After Sort "); 
    display(head); 
    return 0; 
}

C++

// C++ program for Quick Sort on Singly Linked List 
  
#include <cstdio> 
#include <iostream> 
using namespace std; 
  
/* a node of the singly linked list */
struct Node { 
    int data; 
    struct Node* next; 
}; 
  
/* A utility function to insert a node at the beginning of 
 * linked list */
void push(struct Node** head_ref, int new_data) 
{ 
    /* allocate node */
    struct Node* new_node = new Node; 
  
    /* put in the data */
    new_node->data = new_data; 
  
    /* link the old list of the new node */
    new_node->next = (*head_ref); 
  
    /* move the head to point to the new node */
    (*head_ref) = new_node; 
} 
  
/* A utility function to print linked list */
void printList(struct Node* node) 
{ 
    while (node != NULL) { 
        printf("%d ", node->data); 
        node = node->next; 
    } 
    printf("\n"); 
} 
  
// Returns the last node of the list 
struct Node* getTail(struct Node* cur) 
{ 
    while (cur != NULL && cur->next != NULL) 
        cur = cur->next; 
    return cur; 
} 
  
// Partitions the list taking the last element as the pivot 
struct Node* partition(struct Node* head, struct Node* end, 
                       struct Node** newHead, 
                       struct Node** newEnd) 
{ 
    struct Node* pivot = end; 
    struct Node *prev = NULL, *cur = head, *tail = pivot; 
  
    // During partition, both the head and end of the list 
    // might change which is updated in the newHead and 
    // newEnd variables 
    while (cur != pivot) { 
        if (cur->data < pivot->data) { 
            // First node that has a value less than the 
            // pivot - becomes the new head 
            if ((*newHead) == NULL) 
                (*newHead) = cur; 
  
            prev = cur; 
            cur = cur->next; 
        } 
        else // If cur node is greater than pivot 
        { 
            // Move cur node to next of tail, and change 
            // tail 
            if (prev) 
                prev->next = cur->next; 
            struct Node* tmp = cur->next; 
            cur->next = NULL; 
            tail->next = cur; 
            tail = cur; 
            cur = tmp; 
        } 
    } 
  
    // If the pivot data is the smallest element in the 
    // current list, pivot becomes the head 
    if ((*newHead) == NULL) 
        (*newHead) = pivot; 
  
    // Update newEnd to the current last node 
    (*newEnd) = tail; 
  
    // Return the pivot node 
    return pivot; 
} 
  
// here the sorting happens exclusive of the end node 
struct Node* quickSortRecur(struct Node* head, 
                            struct Node* end) 
{ 
    // base condition 
    if (!head || head == end) 
        return head; 
  
    Node *newHead = NULL, *newEnd = NULL; 
  
    // Partition the list, newHead and newEnd will be 
    // updated by the partition function 
    struct Node* pivot 
        = partition(head, end, &newHead, &newEnd); 
  
    // If pivot is the smallest element - no need to recur 
    // for the left part. 
    if (newHead != pivot) { 
        // Set the node before the pivot node as NULL 
        struct Node* tmp = newHead; 
        while (tmp->next != pivot) 
            tmp = tmp->next; 
        tmp->next = NULL; 
  
        // Recur for the list before pivot 
        newHead = quickSortRecur(newHead, tmp); 
  
        // Change next of last node of the left half to 
        // pivot 
        tmp = getTail(newHead); 
        tmp->next = pivot; 
    } 
  
    // Recur for the list after the pivot element 
    pivot->next = quickSortRecur(pivot->next, newEnd); 
  
    return newHead; 
} 
  
// The main function for quick sort. This is a wrapper over 
// recursive function quickSortRecur() 
void quickSort(struct Node** headRef) 
{ 
    (*headRef) 
        = quickSortRecur(*headRef, getTail(*headRef)); 
    return; 
} 
  
// Driver's code 
int main() 
{ 
    struct Node* a = NULL; 
    push(&a, 5); 
    push(&a, 20); 
    push(&a, 4); 
    push(&a, 3); 
    push(&a, 30); 
  
    cout << "Linked List before sorting \n"; 
    printList(a); 
  
    // Function call 
    quickSort(&a); 
  
    cout << "Linked List after sorting \n"; 
    printList(a); 
  
    return 0; 
}

Java

// Java program for Quick Sort on Singly Linked List 
  
/*Sort a linked list using quick sort*/
public class QuickSortLinkedList { 
    static class Node { 
  
        int data; 
        Node next; 
  
        Node(int d) 
        { 
            this.data = d; 
            this.next = null; 
        } 
    } 
  
    Node head; 
  
    void addNode(int data) 
    { 
        if (head == null) { 
            head = new Node(data); 
            return; 
        } 
  
        Node curr = head; 
        while (curr.next != null) 
            curr = curr.next; 
  
        Node newNode = new Node(data); 
        curr.next = newNode; 
    } 
  
    void printList(Node n) 
    { 
        while (n != null) { 
            System.out.print(n.data); 
            System.out.print(" "); 
            n = n.next; 
        } 
    } 
  
    // Takes first and last node, 
    // but do not break any links in 
    // the whole linked list 
    Node partitionLast(Node start, Node end) 
    { 
        if (start == end || start == null || end == null) 
            return start; 
  
        Node pivot_prev = start; 
        Node curr = start; 
        int pivot = end.data; 
  
        // iterate till one before the end, 
        // no need to iterate till the end 
        // because end is pivot 
        while (start != end) { 
            if (start.data < pivot) { 
  
                // keep tracks of last modified item 
                pivot_prev = curr; 
                int temp = curr.data; 
                curr.data = start.data; 
                start.data = temp; 
                curr = curr.next; 
            } 
            start = start.next; 
        } 
  
        // Swap the position of curr i.e. 
        // next suitable index and pivot 
        int temp = curr.data; 
        curr.data = pivot; 
        end.data = temp; 
  
        // Return one previous to current 
        // because current is now pointing to pivot 
        return pivot_prev; 
    } 
  
    void sort(Node start, Node end) 
    { 
        if (start == null || start == end 
            || start == end.next) 
            return; 
  
        // Split list and partition recurse 
        Node pivot_prev = partitionLast(start, end); 
        sort(start, pivot_prev); 
  
        // If pivot is picked and moved to the start, 
        // that means start and pivot is same 
        // so pick from next of pivot 
        if (pivot_prev != null && pivot_prev == start) 
            sort(pivot_prev.next, end); 
  
        // If pivot is in between of the list, 
        // start from next of pivot, 
        // since we have pivot_prev, so we move two nodes 
        else if (pivot_prev != null
                 && pivot_prev.next != null) 
            sort(pivot_prev.next.next, end); 
    } 
  
    // Driver's Code 
    public static void main(String[] args) 
    { 
        QuickSortLinkedList list 
            = new QuickSortLinkedList(); 
        list.addNode(30); 
        list.addNode(3); 
        list.addNode(4); 
        list.addNode(20); 
        list.addNode(5); 
  
        Node n = list.head; 
        while (n.next != null) 
            n = n.next; 
  
        System.out.println("Linked List before sorting"); 
        list.printList(list.head); 
  
        // Function call 
        list.sort(list.head, n); 
  
        System.out.println("\nLinked List after sorting"); 
        list.printList(list.head); 
    } 
} 
  
// This code is contributed by trinadumca

Python3

''' 
  
sort a linked list using quick sort 
  
'''
  
  
class Node: 
    def __init__(self, val): 
        self.data = val 
        self.next = None
  
  
class QuickSortLinkedList: 
  
    def __init__(self): 
        self.head = None
  
    def addNode(self, data): 
        if (self.head == None): 
            self.head = Node(data) 
            return
  
        curr = self.head 
        while (curr.next != None): 
            curr = curr.next
  
        newNode = Node(data) 
        curr.next = newNode 
  
    def printList(self, n): 
        while (n != None): 
            print(n.data, end=" ") 
            n = n.next
  
    ''' takes first and last node,but do not 
    break any links in    the whole linked list'''
  
    def partitionLast(self, start, end): 
        if (start == end or start == None or end == None): 
            return start 
  
        pivot_prev = start 
        curr = start 
        pivot = end.data 
  
        '''iterate till one before the end,  
        no need to iterate till the end because end is pivot'''
  
        while (start != end): 
            if (start.data < pivot): 
  
                # keep tracks of last modified item 
                pivot_prev = curr 
                temp = curr.data 
                curr.data = start.data 
                start.data = temp 
                curr = curr.next
            start = start.next
  
        '''swap the position of curr i.e.  
        next suitable index and pivot'''
  
        temp = curr.data 
        curr.data = pivot 
        end.data = temp 
  
        ''' return one previous to current because  
        current is now pointing to pivot '''
        return pivot_prev 
  
    def sort(self, start, end): 
        if(start == None or start == end or start == end.next): 
            return
  
        # split list and partition recurse 
        pivot_prev = self.partitionLast(start, end) 
        self.sort(start, pivot_prev) 
  
        ''' 
        if pivot is picked and moved to the start, 
        that means start and pivot is same  
        so pick from next of pivot 
        '''
        if(pivot_prev != None and pivot_prev == start): 
            self.sort(pivot_prev.next, end) 
  
        # if pivot is in between of the list,start from next of pivot, 
        # since we have pivot_prev, so we move two nodes 
        elif (pivot_prev != None and pivot_prev.next != None): 
            self.sort(pivot_prev.next.next, end) 
  
  
if __name__ == "__main__": 
    ll = QuickSortLinkedList() 
    ll.addNode(30) 
    ll.addNode(3) 
    ll.addNode(4) 
    ll.addNode(20) 
    ll.addNode(5) 
  
    N = ll.head 
    while (N.next != None): 
        N = N.next
  
    print("\nLinked List before sorting") 
    ll.printList(ll.head) 
  
    # Function call 
    ll.sort(ll.head, N) 
  
    print("\nLinked List after sorting") 
    ll.printList(ll.head) 
  
    # This code is contributed by humpheykibet. 

C#

// C# program for Quick Sort on 
// Singly Linked List 
using System; 
  
/*Sort a linked list using quick sort*/
class GFG { 
    public class Node { 
        public int data; 
        public Node next; 
  
        public Node(int d) 
        { 
            this.data = d; 
            this.next = null; 
        } 
    } 
  
    Node head; 
  
    void addNode(int data) 
    { 
        if (head == null) { 
            head = new Node(data); 
            return; 
        } 
  
        Node curr = head; 
        while (curr.next != null) 
            curr = curr.next; 
  
        Node newNode = new Node(data); 
        curr.next = newNode; 
    } 
  
    void printList(Node n) 
    { 
        while (n != null) { 
            Console.Write(n.data); 
            Console.Write(" "); 
            n = n.next; 
        } 
    } 
  
    // takes first and last node, 
    // but do not break any links in 
    // the whole linked list 
    Node partitionLast(Node start, Node end) 
    { 
        if (start == end || start == null || end == null) 
            return start; 
  
        Node pivot_prev = start; 
        Node curr = start; 
        int pivot = end.data; 
  
        // iterate till one before the end, 
        // no need to iterate till the end 
        // because end is pivot 
        int temp; 
        while (start != end) { 
  
            if (start.data < pivot) { 
                // keep tracks of last modified item 
                pivot_prev = curr; 
                temp = curr.data; 
                curr.data = start.data; 
                start.data = temp; 
                curr = curr.next; 
            } 
            start = start.next; 
        } 
  
        // swap the position of curr i.e. 
        // next suitable index and pivot 
        temp = curr.data; 
        curr.data = pivot; 
        end.data = temp; 
  
        // return one previous to current 
        // because current is now pointing to pivot 
        return pivot_prev; 
    } 
  
    void sort(Node start, Node end) 
    { 
        if (start == end) 
            return; 
  
        // split list and partition recurse 
        Node pivot_prev = partitionLast(start, end); 
        sort(start, pivot_prev); 
  
        // if pivot is picked and moved to the start, 
        // that means start and pivot is same 
        // so pick from next of pivot 
        if (pivot_prev != null && pivot_prev == start) 
            sort(pivot_prev.next, end); 
  
        // if pivot is in between of the list, 
        // start from next of pivot, 
        // since we have pivot_prev, so we move two nodes 
        else if (pivot_prev != null
                 && pivot_prev.next != null) 
            sort(pivot_prev.next.next, end); 
    } 
  
    // Driver Code 
    public static void Main(String[] args) 
    { 
        GFG list = new GFG(); 
        list.addNode(30); 
        list.addNode(3); 
        list.addNode(4); 
        list.addNode(20); 
        list.addNode(5); 
  
        Node N = list.head; 
        while (N.next != null) 
            N = N.next; 
  
        Console.WriteLine("Linked List before sorting"); 
        list.printList(list.head); 
  
        // Function call 
        list.sort(list.head, N); 
  
        Console.WriteLine("\nLinked List after sorting"); 
        list.printList(list.head); 
    } 
} 
  
// This code is contributed by 29AjayKumar

Javascript

// javascript program for Quick Sort on Singly Linked List 
  
/*sort a linked list using quick sort*/
  
     class Node { 
        constructor(val) { 
            this.data = val; 
            this.next = null; 
        } 
    } 
  
    var head; 
  
    function addNode(data) { 
        if (head == null) { 
            head = new Node(data); 
            return; 
        } 
  
        var curr = head; 
        while (curr.next != null) 
            curr = curr.next; 
  
        var newNode = new Node(data); 
        curr.next = newNode; 
    } 
  
    function printList( n) { 
        while (n != null) { 
            document.write(n.data); 
            document.write(" "); 
            n = n.next; 
        } 
    } 
  
    // takes first and last node, 
    // but do not break any links in 
    // the whole linked list 
    function partitionLast( start,  end) { 
        if (start == end || start == null || end == null) 
            return start; 
  
        var pivot_prev = start; 
        var curr = start; 
        var pivot = end.data; 
  
        // iterate till one before the end, 
        // no need to iterate till the end 
        // because end is pivot 
        while (start != end) { 
            if (start.data < pivot) { 
                // keep tracks of last modified item 
                pivot_prev = curr; 
                var temp = curr.data; 
                curr.data = start.data; 
                start.data = temp; 
                curr = curr.next; 
            } 
            start = start.next; 
        } 
  
        // swap the position of curr i.e. 
        // next suitable index and pivot 
        var temp = curr.data; 
        curr.data = pivot; 
        end.data = temp; 
  
        // return one previous to current 
        // because current is now pointing to pivot 
        return pivot_prev; 
    } 
  
    function sort( start,  end) { 
        if (start == null || start == end || start == end.next) 
            return; 
  
        // split list and partition recurse 
        var pivot_prev = partitionLast(start, end); 
        sort(start, pivot_prev); 
  
        // if pivot is picked and moved to the start, 
        // that means start and pivot is same 
        // so pick from next of pivot 
        if (pivot_prev != null && pivot_prev == start) 
            sort(pivot_prev.next, end); 
  
        // if pivot is in between of the list, 
        // start from next of pivot, 
        // since we have pivot_prev, so we move two nodes 
        else if (pivot_prev != null && pivot_prev.next != null) 
            sort(pivot_prev.next.next, end); 
    } 
  
    // Driver Code 
      
        addNode(30); 
        addNode(3); 
        addNode(4); 
        addNode(20); 
        addNode(5); 
  
        var n = head; 
        while (n.next != null) 
            n = n.next; 
  
        document.write("Linked List before sorting<br/>"); 
        printList(head); 
  
        sort(head, n); 
  
        document.write("<br/>Linked List after sorting<br/>"); 
        printList(head); 
  
// This code contributed by umadevi9616

Output

Linked List before sorting 
30 3 4 20 5 
Linked List after sorting 
3 4 5 20 30

Time Complexity: O(N * log N), It takes O(N²) time in the worst case and O(N log N) in the average or best case.
Auxiliary Space: O(N), As extra space is used in the recursion call stack.

Suggest improvement

QuickSort on Doubly Linked List

Why quicksort is better than mergesort ?

Share your thoughts in the comments

QuickSort using different languages

Iterative QuickSort

Different implementations of QuickSort

Visualization of QuickSort

Partitions in QuickSort

Some problems on QuickSort