Quick Sort on SIngly Linked List

Given a linked list, we will sort the linked list using quick sort.

Example

Linked List before sorting
23 ->1 ->50 ->15 ->16 ->6

Linked List after sorting
1 ->6 ->15 ->16 ->23 ->50

Time Complexity : O()

In this method the main idea is to swap pointers rather than swaping data

Algorithm

Partition Algorithm

1. Take rightmost element as the pivot

Traverse through the list

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

  b. else, keep it in same position

QuickSort Algorithm

1. Call Partition(), which places pivot at right position and returns the pivot

2.  Find the tail node of the left sublist ie, left side of the pivot and recur for left list

3.  Now, recur for right list

C++ 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;
    while(temp!=NULL) //till the list ends (NULL marks ending of list)
        {
            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;
}

 

Translate »