Use Quick Sort to Sort a Linear Linked List

Quicksort algorithm is based on the concept of divide and conquer, where we do all the main work of sorting while dividing the given data structure(can be an array or in this case a Linked List) and during merging the data back, absolutely no processing is done, data is simply combined back together.

Quick Sort is also known as Partition-Exchange Sort.

In the quick sort algorithm, the given dataset is divided into three sections,

1. Data elements less than the pivot

2. The data element which is the pivot

3. And the data elements are greater than the pivot.

Also in this case, when we want to use quicksort with a linked list, the main idea is to swap pointers(in the node) rather than swapping data.

Steps of the Algorithm:

The whole algorithm can be divided into two parts,

Partition:

1. Take the rightmost element as the pivot.

2. Traverse through the list:

   1. If the current node has a value greater than the pivot, we will move it after the tail

   2. else, keep it in the same position.

Quick Sort:

1. Call the partition() method, which will place the pivot at the right position and will return the pivot

2. Find the tail node of the left sublist i.e., left side of the pivot and recur the whole algorithm for the left list.

3. Now, recur the algorithm for the right list.

Implementation in C/C++

As we have seen the algorithm, let's now move on to the actual program:

#include <iostream>

#include <cstdio>

using namespace std;

// a node of the singly linked list
struct LLNode {
    int data;
    LLNode *next;
};

// utility function to insert a LLNode at the beginning of linked list
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
    LLNode *curr = new LLNode;
    // make a new LLNode with this data and next pointing to NULL
    curr->data = dataToBeInserted;
    curr->next = NULL;

    if(*head == NULL) {
        // if list is empty then set the current formed LLNode as head of list    
        *head=curr;
    }
    else {   
        /*     make the next of the current LLNode point to the 
            present head and make the current LLNode as the new head
        */
        curr->next = *head;
        *head = curr;
    }
    //  O(1) constant time
}

// A utility function to print linked list
void display(LLNode**head)
{

    LLNode *temp = *head;
    // till the list ends (NULL marks ending of list)
    while(temp!=NULL) {

        if(temp->next!=NULL)
            cout<<temp->data<<" ->";
        else
            cout<<temp->data;

        temp=temp->next;     // move to next node
    }
    // O(number of nodes)
    cout<<endl;
}

// Returns the last node of the list
LLNode *getTail(LLNode *cur)
{
    while (cur != NULL && cur->next != NULL)
        cur = cur->next;
    
    return cur;
}

// Partitions the list taking the last element as the pivot
LLNode *partition(LLNode *head, LLNode *end, LLNode **newHead, LLNode **newEnd)
{
    LLNode *pivot = end;
    LLNode *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 LLNode is greater than pivot
                Move cur LLNode to next of tail, and change tail
            */
            if(prev)
                prev->next = cur->next;
            
            LLNode *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 LLNode
    return pivot;
}

//  here the sorting happens exclusive of the end node
LLNode *quickSortRecur(LLNode *head, LLNode *end)
{
    // base condition
    if (!head || head == end)
        return head;

    LLNode *newHead = NULL, *newEnd = NULL;

    /*    Partition the list, newHead and newEnd will be updated
        by the partition function
    */

    LLNode *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 LLNode before the pivot LLNode as NULL

        LLNode *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 LLNode 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(LLNode **headRef)
{
    (*headRef) = quickSortRecur(*headRef, getTail(*headRef));
    return;
}

// Driver program to test above functions
int main() {

    LLNode *head = NULL;

    LLNode *tail = NULL;

    insertAtBeginning(&head, 6);

    insertAtBeginning(&head, 16);

    insertAtBeginning(&head, 15);

    insertAtBeginning(&head, 50);

    insertAtBeginning(&head, 1);

    insertAtBeginning(&head, 23);

    cout << "Linked List before sorting \n";

    display(&head);

    quickSort(&head);

    cout << "Linked List after sorting \n";

    display(&head);

    return 0;

}

Time Complexity of the Algorithm

The worst case time complexity of this algorithm is O(n^2) and the average case complexity is O(nlogn).

Conclusion

Sorting a linear linked list using Quick Sort can be a powerful technique to efficiently organize data and improve performance. In this article, we have explored the intricacies of applying Quick Sort to linked lists, understanding the partitioning process and the recursive nature of the algorithm. By leveraging the inherent properties of linked lists and the efficiency of Quick Sort, you can achieve optimal time complexity for sorting operations.

Frequently Asked Questions(FAQs)

1. Can Quick Sort be applied to a linear linked list?

Yes, Quick Sort can be applied to a linear linked list by leveraging the principles of the algorithm and adapting it to work with the structure of linked lists.

2. How does Quick Sort work for sorting a linear linked list?

Quick Sort for a linear linked list involves selecting a pivot element, partitioning the list around the pivot, recursively sorting the sublists, and reassembling them to obtain the sorted list.

3. What are the advantages of using Quick Sort for sorting a linear linked list?

Quick Sort offers several advantages, such as efficient time complexity (average-case O(n log n)), in-place sorting without requiring additional memory, and adaptability to varying data distributions.

4. Are there any considerations or challenges when using Quick Sort for a linear linked list?

Yes, some considerations include handling the choice of pivot element, managing pointers and references in the linked list, handling duplicate values, and addressing edge cases such as empty lists or lists with a single element.

5. Are there alternative sorting algorithms for linear linked lists?

Yes, there are alternative sorting algorithms such as Merge Sort and Insertion Sort that can be applied to linear linked lists. Each algorithm has its own advantages and considerations, so it's worth exploring different approaches to find the most suitable one for your specific requirements.

You may also like:

• What is Hashing?

• Trie Data Structure

• Insertion(Adding a new Node) in a Binary Tree Data Structure

• Using Merge Sort to Sort a Linked List