Program on Quicksort on Linked List in C++

In this tutorial, we are going to learn about Quicksort on Linked List in C++. Firstly we are going to look at linked list. Secondly about the quicksort and finally to combine them.

Introduction

Linked List

Linked list is a data type in which nodes are linked with each other. In a linked list node can be of different data type and is created using by a structure in c++. Single linked list contains a single link to the next node.




Quicksort

Quicksort is performed using the concept of divide and conquer.  It takes an element as pivot and partitions the given array around the picked pivot. It is one of the fastest sorting algorithms.

Perform Quicksort on Linked List in C++

Firstly, we have to create a program to create a linked list and then fill it up with data.

Secondly, in the created linked list we apply quicksort.

Code:

#include <iostream> 
#include <cstdio> 
using namespace std; 
  
struct Node 
{ 
    int data; 
    struct Node *next; 
}; 
  
void insert(struct Node** head_ref, int new_data) 
{ 
    struct Node* new_node = new Node; 
  
    new_node->data  = new_data; 
  
    new_node->next = (*head_ref); 
  
    (*head_ref)    = new_node; 
}
  
void print(struct Node *node) 
{ 
    while (node != NULL) 
    { 
        cout<<node->data<<" "; 
        node = node->next; 
    } 
    cout<<"\n"; 
} 
  
struct Node *getTail(struct Node *cur) 
{ 
    while (cur != NULL && cur->next != NULL) 
        cur = cur->next; 
    return cur; 
} 
  
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; 
  
    while (cur != pivot) 
    { 
        if (cur->data < pivot->data) 
        {  
            if ((*newHead) == NULL) 
                (*newHead) = cur; 
  
            prev = cur;   
            cur = cur->next; 
        } 
        else
        { 

            if (prev) 
                prev->next = cur->next; 
            struct Node *tmp = cur->next; 
            cur->next = NULL; 
            tail->next = cur; 
            tail = cur; 
            cur = tmp; 
        } 
    } 
  
    if ((*newHead) == NULL) 
        (*newHead) = pivot; 
  
    (*newEnd) = tail; 
  
    return pivot; 
} 
  
  
struct Node *quickSortRecur(struct Node *head, struct Node *end) 
{ 
    if (!head || head == end) 
        return head; 
  
    Node *newHead = NULL, *newEnd = NULL; 
  
    struct Node *pivot = partition(head, end, &newHead, &newEnd); 
  
    if (newHead != pivot) 
    { 
        struct Node *tmp = newHead; 
        while (tmp->next != pivot) 
            tmp = tmp->next; 
        tmp->next = NULL; 
  
        newHead = quickSortRecur(newHead, tmp); 
  
        tmp = getTail(newHead); 
        tmp->next =  pivot; 
    } 
  
    pivot->next = quickSortRecur(pivot->next, newEnd); 
  
    return newHead; 
} 
   
void quickSort(struct Node **headRef) 
{ 
    (*headRef) = quickSortRecur(*headRef, getTail(*headRef)); 
    return; 
} 
  
int main() 
{ 
    struct Node *start = NULL; 
    int t,num;
    cout<<"Enter the number of elements: ";
    cin>>t;
    while(t--){
    	cin>>num;
    	insert(&start, num);
  }
  
    quickSort(&start); 
  
    cout << "Linked List after sorting \n"; 
    print(start); 
  
    return 0; 
}

INPUT:

Enter the number of elements: 5
2
1
6
4
3

OUTPUT:

Linked List after sorting
1 2 3 4 6

Explanation:

Firstly the number of elements is taken in input are insert inside the linked list. Then linked list is sorted using quicksort.

Written below is the algorithm for quicksort for linked list:

  1. After selecting an element as pivot, which is the last element of the linked list in our case, we divide the array for the first time.
  2. In quicksort, we call this partition. It is not simple, breaking down of linked list into 2 linked lists, but in case of partitioning, the linked list elements are so positioned that all the elements smaller than the pivot will be on the left side of the pivot and all the elements greater than the pivot will be on the right side of it.
  3. And the pivot element will be at its final sorted position.
  4. The elements to the left and right, may not be sorted.
  5. Then we pick linked lists, elements on the left of pivot and elements on the right of pivot, and we perform partition on them by choosing a pivot in the linked lists.

Also Checkout:

Count the number of occurrences of an element in a linked list in c++


Leave a Reply

Your email address will not be published. Required fields are marked *