QuickSort on Singly Linked List

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

According to the problem statement, We will be given a singly linked list and we need to sort the list using Quick sort sorting algorithm.

Before going to the approach section, we need to understand Quicksort Algorithm thoroughly. It is easier to understand the QuickSort algorithm on an array; that’s why we will first learn to apply quicksort on an array, and then learn how to apply the Quicksort algorithm on a singly linked list.

Introduction – Quick Sort

  • QuickSort is a Divide and Conquer algorithm, so it is also a recursive algorithm.
  • Here, We pick an element as a pivot and partition the given array around the picked pivot element.
  • After partition, we arrange the elements such that all the elements smaller than the pivot element will be before the pivot, and all the elements greater than the pivot element will be after the pivot.
  • After this, we will call Quick sort again on the elements from starting to pivot-1 and pivot+1 to the end.
  • We will continue to call Quick sort till we hit the base case.

Algorithm (Quick Sort)

  • We have to first pick an element of the array as a pivot.
  • We can choose any element as a pivot element, e.g. starting element of the array, last element of the array, middle element of the array, etc.
  • We will take the first element of the array as the pivot element.
  • Now we will count the number of elements that are smaller than the pivot element in the array.
  • Now we have to move the pivot element to its correct position in the array.
  • Initialize K = 0, K is the correct position of the pivot element.
    • K = (pivot index + the number of elements smaller than the pivot element in the array).
  • After swapping the pivot element with the element at the index K, arrange the elements such that all elements smaller than the pivot element will be before the pivot, and all elements greater than the pivot element will be after the pivot.
  • After this, we will call Quicksort again on the elements from starting index to pivot-1 and pivot+1 to the end index. We will continue to call Quicksort till we hit the base case.

Dry Run

Code Implementation

#include<bits/stdc++.h>
using namespace std;

int partition(int* arr, int si, int ei){

    int count = 0;
    // count of numbers of elements smaller than arr[0]

    int i = si+1;
    while(i<=ei){
        if(arr[i]<arr[si]){
            count++;
        }
        i++;
    }

    int pivot = si + count;

    swap(arr[si], arr[pivot]);
    
    int k = si;
    int j = ei;


    // Arrange elements such that all elements before pivot 
    // will be smaller than pivot element and all elements greater than pivot element after pivot.
    while(k<pivot && j>pivot){
        if(arr[k]>arr[pivot] && arr[j]<arr[pivot]){
            swap(arr[k], arr[j]);
            k++;
            j--;
        }else if(arr[k]<arr[pivot]){
            k++;
        }else if(arr[j]>arr[pivot]){
            j--;
        }
    }

    return pivot;
}


void quickSort(int* arr, int si, int ei){
    //Base case
    if(si>=ei){
        return;
    }


    // function for partition around pivot
    int pivot = partition(arr, si, ei);

    quickSort(arr, si, pivot-1);
    quickSort(arr, pivot+1, ei);
}

int main(){
    int n;
    cin>>n;

    int* arr = new int[n];

    for(int i=0; i<n; i++){
        cin>>arr[i];
    }

    quickSort(arr, 0, n-1);

    for(int i=0; i<n; i++){
        cout<<arr[i]<<" ";
    }
}

public class QuickSort 
{
	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 paritionLast(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 = paritionLast(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)
    {
		QuickSort list= new QuickSort();
		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);

		list.sort(list.head, n);

		System.out.println("\nLinked List after sorting");
		list.printList(list.head);
	}
}

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

	def paritionLast(self,start, end):
		if (start == end or start == None or end == None):
			return start

		pivot_prev = start
		curr = start
		pivot = end.data


		while (start != end):
			if (start.data < pivot):
			
				pivot_prev = curr
				temp = curr.data
				curr.data = start.data
				start.data = temp
				curr = curr.next
			start = start.next


		temp = curr.data
		curr.data = pivot
		end.data = temp

		return pivot_prev

	def sort(self, start, end):
		if(start == None or start == end or start == end.next):
			return

		pivot_prev = self.paritionLast(start, end)
		self.sort(start, pivot_prev)

		if(pivot_prev != None and pivot_prev == start):
			self.sort(pivot_prev.next, end)

		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("Linked List before sorting")
	ll.printList(ll.head)

	ll.sort(ll.head, n)

	print("\nLinked List after sorting");
	ll.printList(ll.head)

Now, we have a good understanding of the QuickSort algorithm. Let’s learn how to apply QuickSort on a singly linked list.

Algorithm

Quick Sort on Singly Linked List:

Initialize a pointer named tail of type node with head, and move it to the last node of the linked list. To get the last node of the linked list, we will traverse through the list until we have found a node whose next is NULL.

Recursive Function: Node quickSortHelper( Node head, Node *tail), it will return the new head after sorting the list.

Base Case: When the head and tail point to the same node or head is NULL, we will just return the head.

Algorithm Steps:
1) We can pick any element as a pivot, but we will pick the last element as a pivot.
2) Make a partition function that will partition the list around the picked pivot.
3) We have already seen that we need to arrange the elements such that all elements smaller than the pivot element will be before the pivot, and all elements greater than the pivot element will be after the pivot; that’s why we will create a partition function.
4) In this partition function, we will traverse through the current list, and :

  • If a node’s data is greater than the pivot’s data, we move it after tail.
  • Else if the node’s data has a smaller value than the tail’s data, we keep it at its current position, i.e, no change in position.
    5) In this partition function, after partition of the nodes around the pivot node, generates two new linked lists. One linked list contains all nodes that are smaller in value than the pivot node and another linked list contains all nodes greater than the pivot node.
    6) The partition function will update 5 pointers that point to the pivot, head and tail pointer of linked list containing all nodes smaller than pivot and head and tail pointer of linked list containing all nodes greater than pivot.
    7) Now we will call quickSortRecur on nodes that are smaller than the pivot node, after that we will again call quickSortRecur on nodes that are greater than the pivot node.
    8) This process continues till we hit the base case and when we hit the base case we start returning from the recursive calls.
    9) When we return back after hitting the base case we will join these two linked lists in such order that our whole linked list remains sorted.

Dry Run

Code Implementation

#include 
using namespace std;

/* Node structure of a singly linked list */
class Node {
public:
    int data;
    Node* next;
};

/* Using this function we will insert a node at the beginning of the linked list */
void push(Node** head_ref, int val){
    Node* newNode = new Node;

    newNode->data = val;

    newNode->next = (*head_ref);

    (*head_ref) = newNode;
}

/* Using this function we will print the content of the linked list */
void printList(Node* node){
    while (node != NULL) {
        cout<data<<" ";
        node = node->next;
    }
    cout<next != NULL)
        cur = cur->next;
    return cur;
}

/* Using this function we will partition the linked list taking the last element of list as pivot */
Node* partition( Node* head,  Node* end,
                     Node** newHead,
                     Node** newEnd)
{
     Node* pivot = end;
     Node *prev = NULL, *cur = head, *tail = pivot;

    // During the time of partition, both the head and end of the list
    // might change and the changes will be updated in the newHead and
    // newEnd variables
    while (cur != pivot) {
        if (cur->data < pivot->data) {
            // The first node that will be having value less than the
            // pivot node value will become the new head
            if ((*newHead) == NULL)
                (*newHead) = cur;

            prev = cur;
            cur = cur->next;
        }
        else // If the value of the cur node is greater than that of the pivot
        {
            // We will move the cur node to next of tail, and will update tail
            if (prev)
                prev->next = cur->next;
             Node* tmp = cur->next;
            cur->next = NULL;
            tail->next = cur;
            tail = cur;
            cur = tmp;
        }
    }

    // If the data of the pivot node is smallest in the
    // current list, then we will make pivot as the head
    if ((*newHead) == NULL)
        (*newHead) = pivot;

    // newEnd will be updated to the current last node
    (*newEnd) = tail;

    // Finally, we will return the pivot node
    return pivot;
}

// Quick sort recursive function
 Node* quickSortRecur( Node* head,
                             Node* end)
{
    // base condition
    if (!head || head == end)
        return head;

    Node *newHead = NULL, *newEnd = NULL;

    // We will call the partition function and it will partition the list
    // and will also update newHead and newEnd
    // it will return the pivot node
     Node* pivot
        = partition(head, end, &newHead, &newEnd);

    // If our pivot is the smallest element in the current list
    // then there is no need to recur for the left part of the list
    if (newHead != pivot) {
         Node* tmp = newHead;
        while (tmp->next != pivot)
            tmp = tmp->next;
        tmp->next = NULL;

        // Now we will recur for the list before the pivot
        newHead = quickSortRecur(newHead, tmp);

        tmp = getTail(newHead);
        tmp->next = pivot;
    }

    // Now we will recur for the list after the pivot
    pivot->next = quickSortRecur(pivot->next, newEnd);

    return newHead;
}

// Ths is the function for quicksort. 
void quickSort(Node** headRef){
    (*headRef)
        = quickSortRecur(*headRef, getTail(*headRef));
    return;
} 


int main(){
    Node* a = NULL;
    push(&a, 8);
    push(&a, 9);
    push(&a, 5);
    push(&a, 3);
    push(&a, 2);
    push(&a, 7);


    cout << "Linked List before sorting \n";
    printList(a);

    quickSort(&a);

    cout << "Linked List after sorting \n";
    printList(a);

    return 0;
}
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 paritionLast(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 = paritionLast(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)
    {
        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);
 
        list.sort(list.head, n);
 
        System.out.println("\nLinked List after sorting");
        list.printList(list.head);
    }
}
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 paritionLast(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.paritionLast(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)
 
    ll.sort(ll.head, n)
 
    print("\nLinked List after sorting");
    ll.printList(ll.head)

Output

Linked List before sorting
7 2 3 5 9 8
Linked List after sorting
2 3 5 7 8 9

Time Complexity: Best case – O(NlogN), Worst case – O(N2).

[forminator_quiz id=”5430″]

So, In this blog, we have learned How to QuickSort on Singly Linked List. This is an important question when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Leave a Reply

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