Skip to main content

Quicksort on singly linked list

The given problem is to implement the Quicksort algorithm on a singly linked list in Java. Quicksort is a popular sorting algorithm known for its efficiency and widely used in various programming applications. In this problem, we have a custom implementation of a singly linked list, and we need to apply the Quicksort algorithm to sort the elements of the linked list in ascending order.

Problem Statement

The problem can be stated as follows: Given a singly linked list, we need to sort its elements using the Quicksort algorithm in ascending order.

Example

Let's consider the following unsorted linked list:

Input 
Linked List: 41 -> 5 -> 7 -> 22 -> 28 -> 63 -> 4 -> 8 -> 2 -> 11
Output
Linked List: 2 -> 4 -> 5 -> 7 -> 8 -> 11 -> 22 -> 28 -> 41 -> 63

Standard Pseudocode for Quicksort on Singly Linked List

quicksort(linked_list, first, last):
    if first == last:
        return
    pivot = partition(linked_list, first, last)
    quicksort(linked_list, first, pivot)
    quicksort(linked_list, pivot.next, last)

partition(linked_list, first, last):
    pivot = first
    front = first
    while front != last:
        if front.data < last.data:
            swap(front.data, pivot.data)
            pivot = pivot.next
        front = front.next
    swap(pivot.data, last.data)
    return pivot

Algorithm Explanation

  1. quicksort(linked_list, first, last):

    • This function is the main driver for the Quicksort algorithm on the linked list.
    • If first == last, it means there is only one node or no node, so there is nothing to sort, and we return from the function.
    • The partition() function is called to find the pivot node and rearrange elements such that elements less than the pivot are on the left and elements greater than the pivot are on the right.
    • Then, we recursively call quicksort() on the left and right partitions of the linked list.

  2. partition(linked_list, first, last):

    • This function finds the pivot node using the last node and rearranges the elements in the linked list around the pivot node.
    • Initially, pivot and front both point to the first node (first).
    • We iterate through the linked list using front as long as it is not the last node.
    • If front.data is less than the last.data (pivot node value), we swap the data of front and pivot nodes, and then move pivot to the next node.
    • After the iteration, we swap the data of pivot and last nodes to place the pivot node in its correct position.
    • Finally, we return the pivot node.

Program Solution

// C Program
// Quicksort on singly linked list

#include <stdio.h>
 //for malloc function
#include <stdlib.h>

//Create 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)
	{
		printf("Memory overflow\n");
	}
	else
	{
		node->data = value;
		node->next = NULL;
		if ( *head == NULL)
		{
			*head = node;
		}
		else
		{
			struct Node *temp = *head;
			//find last node
			while (temp->next != NULL)
			{
				temp = temp->next;
			}
			//add node at last possition
			temp->next = node;
		}
	}
}
//Display 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;
	}
}
//Find 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;
}
//Set of given last node position to its proper position
struct Node *parition(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;
			//Swap node value
			temp = first->data;
			first->data = front->data;
			front->data = temp;
			//Visit to next node
			first = first->next;
		}
		//Visit to next node
		front = front->next;
	}
	//Change last node value to current node
	temp = first->data;
	first->data = last->data;
	last->data = temp;
	return pivot;
}
//Perform quick sort in given linked list
void quick_sort(struct Node *first, struct Node *last)
{
	if (first == last)
	{
		return;
	}
	struct Node *pivot = parition(first, last);
	if (pivot != NULL && pivot->next != NULL)
	{
		quick_sort(pivot->next, last);
	}
	if (pivot != NULL && first != pivot)
	{
		quick_sort(first, pivot);
	}
}
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);
	quick_sort(head, last_node(head));
	printf("\n After Sort ");
	display(head);
	return 0;
}

Output

 Before Sort
 Linked List :  41  5  7  22  28  63  4  8  2  11
 After Sort
 Linked List :  2  4  5  7  8  11  22  28  41  63
// Java Program
// Quicksort on singly linked list

//Node of LinkedList
class Node
{
	public int data;
	public Node next;
	public Node(int data)
	{
		//set node value
		this.data = data;
		this.next = null;
	}
}
class MyLinkedList
{
	public Node head;
	public Node tail;
	//Class constructors
	public MyLinkedList()
	{
		this.head = null;
		this.tail = null;
	}
	//insert node at last of linke list
	public void insert(int value)
	{
		//Create a node
		Node node = new Node(value);
		if (this.head == null)
		{
			//When linked list empty add first node
			this.head = node;
			this.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this.tail.next = node;
			this.tail = node;
		}
	}
	//Display linked list nodes
	public void display()
	{
		if (this.head != null)
		{
			System.out.print("\n Linked List :");
			Node temp = this.head;
			while (temp != null)
			{
				System.out.print(" " + temp.data);
				temp = temp.next;
				if (temp == this.head)
				{
					//avoid loop
					return;
				}
			}
		}
		else
		{
			System.out.println("Empty Linked List");
		}
	}
	//Find last node of linked list
	public Node last_node()
	{
		Node temp = this.head;
		while (temp != null && temp.next != null)
		{
			temp = temp.next;
		}
		return temp;
	}
	//Set of given last node position to its proper position
	public Node parition(Node first, Node last)
	{
		//Get first node of given linked list
		Node pivot = first;
		Node front = first;
		int temp = 0;
		while (front != null && front != last)
		{
			if (front.data < last.data)
			{
				pivot = first;
				//Swap node value
				temp = first.data;
				first.data = front.data;
				front.data = temp;
				//Visit to next node
				first = first.next;
			}
			//Visit to next node
			front = front.next;
		}
		//Change last node value to current node
		temp = first.data;
		first.data = last.data;
		last.data = temp;
		return pivot;
	}
	//Perform quick sort in given linked list
	public void quick_sort(Node first, Node last)
	{
		if (first == last)
		{
			return;
		}
		//Find pivot node
		Node pivot = parition(first, last);
		if (pivot != null && pivot.next != null)
		{
			quick_sort(pivot.next, last);
		}
		if (pivot != null && first != pivot)
		{
			quick_sort(first, pivot);
		}
	}
	public static void main(String[] args)
	{
		MyLinkedList obj = new MyLinkedList();
		//Create linked list
		obj.insert(41);
		obj.insert(5);
		obj.insert(7);
		obj.insert(22);
		obj.insert(28);
		obj.insert(63);
		obj.insert(4);
		obj.insert(8);
		obj.insert(2);
		obj.insert(11);
		System.out.print("\n Before Sort ");
		obj.display();
		obj.quick_sort(obj.head, obj.last_node());
		System.out.print("\n After Sort ");
		obj.display();
	}
}

Output

 Before Sort
 Linked List : 41 5 7 22 28 63 4 8 2 11
 After Sort
 Linked List : 2 4 5 7 8 11 22 28 41 63
//Include header file
#include <iostream>
using namespace std;

// C++ Program
// Quicksort on singly linked list

//Node of LinkedList
class Node
{
	public: int data;
	Node * next;
	Node(int data)
	{
		//set node value
		this->data = data;
		this->next = NULL;
	}
};
class MyLinkedList
{
	public: Node * head;
	Node * tail;
	//Class constructors
	MyLinkedList()
	{
		this->head = NULL;
		this->tail = NULL;
	}
	//insert node at last of linke list
	void insert(int value)
	{
		//Create a node
		Node * node = new Node(value);
		if (this->head == NULL)
		{
			//When linked list empty add first node
			this->head = node;
			this->tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this->tail->next = node;
			this->tail = node;
		}
	}
	//Display linked list nodes
	void display()
	{
		if (this->head != NULL)
		{
			cout << "\n Linked List :";
			Node * temp = this->head;
			while (temp != NULL)
			{
				cout << " " << temp->data;
				temp = temp->next;
				if (temp == this->head)
				{
					//avoid loop
					return;
				}
			}
		}
		else
		{
			cout << "Empty Linked List";
		}
	}
	//Find last node of linked list
	Node * last_node()
	{
		Node * temp = this->head;
		while (temp != NULL && temp->next != NULL)
		{
			temp = temp->next;
		}
		return temp;
	}
	//Set of given last node position to its proper position
	Node * parition(Node * first, Node * last)
	{
		//Get first node of given linked list
		Node * pivot = first;
		Node * front = first;
		int temp = 0;
		while (front != NULL && front != last)
		{
			if (front->data < last->data)
			{
				pivot = first;
				//Swap node value
				temp = first->data;
				first->data = front->data;
				front->data = temp;
				//Visit to next node
				first = first->next;
			}
			//Visit to next node
			front = front->next;
		}
		//Change last node value to current node
		temp = first->data;
		first->data = last->data;
		last->data = temp;
		return pivot;
	}
	//Perform quick sort in given linked list
	void quick_sort(Node * first, Node * last)
	{
		if (first == last)
		{
			return;
		}
		//Find pivot node
		Node * pivot = this->parition(first, last);
		if (pivot != NULL && pivot->next != NULL)
		{
			this->quick_sort(pivot->next, last);
		}
		if (pivot != NULL && first != pivot)
		{
			this->quick_sort(first, pivot);
		}
	}
};
int main()
{
	MyLinkedList obj = MyLinkedList();
	//Create linked list
	obj.insert(41);
	obj.insert(5);
	obj.insert(7);
	obj.insert(22);
	obj.insert(28);
	obj.insert(63);
	obj.insert(4);
	obj.insert(8);
	obj.insert(2);
	obj.insert(11);
	cout << "\n Before Sort ";
	obj.display();
	obj.quick_sort(obj.head, obj.last_node());
	cout << "\n After Sort ";
	obj.display();
	return 0;
}

Output

 Before Sort
 Linked List : 41 5 7 22 28 63 4 8 2 11
 After Sort
 Linked List : 2 4 5 7 8 11 22 28 41 63
//Include namespace system
using System;
// C# Program
// Quicksort on singly linked list

//Node of LinkedList
class Node
{
	public int data;
	public Node next;
	public Node(int data)
	{
		//set node value
		this.data = data;
		this.next = null;
	}
}
class MyLinkedList
{
	public Node head;
	public Node tail;
	//Class constructors
	public MyLinkedList()
	{
		this.head = null;
		this.tail = null;
	}
	//insert node at last of linke list
	public void insert(int value)
	{
		//Create a node
		Node node = new Node(value);
		if (this.head == null)
		{
			//When linked list empty add first node
			this.head = node;
			this.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this.tail.next = node;
			this.tail = node;
		}
	}
	//Display linked list nodes
	public void display()
	{
		if (this.head != null)
		{
			Console.Write("\n Linked List :");
			Node temp = this.head;
			while (temp != null)
			{
				Console.Write(" " + temp.data);
				temp = temp.next;
				if (temp == this.head)
				{
					//avoid loop
					return;
				}
			}
		}
		else
		{
			Console.WriteLine("Empty Linked List");
		}
	}
	//Find last node of linked list
	public Node last_node()
	{
		Node temp = this.head;
		while (temp != null && temp.next != null)
		{
			temp = temp.next;
		}
		return temp;
	}
	//Set of given last node position to its proper position
	public Node parition(Node first, Node last)
	{
		//Get first node of given linked list
		Node pivot = first;
		Node front = first;
		int temp = 0;
		while (front != null && front != last)
		{
			if (front.data < last.data)
			{
				pivot = first;
				//Swap node value
				temp = first.data;
				first.data = front.data;
				front.data = temp;
				//Visit to next node
				first = first.next;
			}
			//Visit to next node
			front = front.next;
		}
		//Change last node value to current node
		temp = first.data;
		first.data = last.data;
		last.data = temp;
		return pivot;
	}
	//Perform quick sort in given linked list
	public void quick_sort(Node first, Node last)
	{
		if (first == last)
		{
			return;
		}
		//Find pivot node
		Node pivot = parition(first, last);
		if (pivot != null && pivot.next != null)
		{
			quick_sort(pivot.next, last);
		}
		if (pivot != null && first != pivot)
		{
			quick_sort(first, pivot);
		}
	}
	public static void Main(String[] args)
	{
		MyLinkedList obj = new MyLinkedList();
		//Create linked list
		obj.insert(41);
		obj.insert(5);
		obj.insert(7);
		obj.insert(22);
		obj.insert(28);
		obj.insert(63);
		obj.insert(4);
		obj.insert(8);
		obj.insert(2);
		obj.insert(11);
		Console.Write("\n Before Sort ");
		obj.display();
		obj.quick_sort(obj.head, obj.last_node());
		Console.Write("\n After Sort ");
		obj.display();
	}
}

Output

 Before Sort
 Linked List : 41 5 7 22 28 63 4 8 2 11
 After Sort
 Linked List : 2 4 5 7 8 11 22 28 41 63
<?php
// Php Program
// Quicksort on singly linked list

//Node of LinkedList
class Node
{
	public $data;
	public $next;

	function __construct($data)
	{
		//set node value
		$this->data = $data;
		$this->next = null;
	}
}
class MyLinkedList
{
	public $head;
	public $tail;
	//Class constructors
	function __construct()
	{
		$this->head = null;
		$this->tail = null;
	}
	//insert node at last of linke list
	public	function insert($value)
	{
		//Create a node
		$node = new Node($value);
		if ($this->head == null)
		{
			//When linked list empty add first node
			$this->head = $node;
			$this->tail = $node;
		}
		else
		{
			//Add new node at end of linked list
			$this->tail->next = $node;
			$this->tail = $node;
		}
	}
	//Display linked list nodes
	public	function display()
	{
		if ($this->head != null)
		{
			echo "\n Linked List :";
			$temp = $this->head;
			while ($temp != null)
			{
				echo " ". $temp->data;
				$temp = $temp->next;
				if ($temp == $this->head)
				{
					//avoid loop
					return;
				}
			}
		}
		else
		{
			echo "Empty Linked List";
		}
	}
	//Find last node of linked list
	public	function last_node()
	{
		$temp = $this->head;
		while ($temp != null && $temp->next != null)
		{
			$temp = $temp->next;
		}
		return $temp;
	}
	//Set of given last node position to its proper position
	public	function parition($first, $last)
	{
		//Get first node of given linked list
		$pivot = $first;
		$front = $first;
		$temp = 0;
		while ($front != null && $front != $last)
		{
			if ($front->data < $last->data)
			{
				$pivot = $first;
				//Swap node value
				$temp = $first->data;
				$first->data = $front->data;
				$front->data = $temp;
				//Visit to next node
				$first = $first->next;
			}
			//Visit to next node
			$front = $front->next;
		}
		//Change last node value to current node
		$temp = $first->data;
		$first->data = $last->data;
		$last->data = $temp;
		return $pivot;
	}
	//Perform quick sort in given linked list
	public	function quick_sort($first, $last)
	{
		if ($first == $last)
		{
			return;
		}
		//Find pivot node
		$pivot = $this->parition($first, $last);
		if ($pivot != null && $pivot->next != null)
		{
			$this->quick_sort($pivot->next, $last);
		}
		if ($pivot != null && $first != $pivot)
		{
			$this->quick_sort($first, $pivot);
		}
	}
}

function main()
{
	$obj = new MyLinkedList();
	//Create linked list
	$obj->insert(41);
	$obj->insert(5);
	$obj->insert(7);
	$obj->insert(22);
	$obj->insert(28);
	$obj->insert(63);
	$obj->insert(4);
	$obj->insert(8);
	$obj->insert(2);
	$obj->insert(11);
	echo "\n Before Sort ";
	$obj->display();
	$obj->quick_sort($obj->head, $obj->last_node());
	echo "\n After Sort ";
	$obj->display();
}
main();

Output

 Before Sort
 Linked List : 41 5 7 22 28 63 4 8 2 11
 After Sort
 Linked List : 2 4 5 7 8 11 22 28 41 63
// Node Js Program
// Quicksort on singly linked list

//Node of LinkedList
class Node
{
	constructor(data)
	{
		//set node value
		this.data = data;
		this.next = null;
	}
}
class MyLinkedList
{
	//Class constructors
	constructor()
	{
		this.head = null;
		this.tail = null;
	}
	//insert node at last of linke list
	insert(value)
	{
		//Create a node
		var node = new Node(value);
		if (this.head == null)
		{
			//When linked list empty add first node
			this.head = node;
			this.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this.tail.next = node;
			this.tail = node;
		}
	}
	//Display linked list nodes
	display()
	{
		if (this.head != null)
		{
			process.stdout.write("\n Linked List :");
			var temp = this.head;
			while (temp != null)
			{
				process.stdout.write(" " + temp.data);
				temp = temp.next;
				if (temp == this.head)
				{
					//avoid loop
					return;
				}
			}
		}
		else
		{
			process.stdout.write("Empty Linked List");
		}
	}
	//Find last node of linked list
	last_node()
	{
		var temp = this.head;
		while (temp != null && temp.next != null)
		{
			temp = temp.next;
		}
		return temp;
	}
	//Set of given last node position to its proper position
	parition(first, last)
	{
		//Get first node of given linked list
		var pivot = first;
		var front = first;
		var temp = 0;
		while (front != null && front != last)
		{
			if (front.data < last.data)
			{
				pivot = first;
				//Swap node value
				temp = first.data;
				first.data = front.data;
				front.data = temp;
				//Visit to next node
				first = first.next;
			}
			//Visit to next node
			front = front.next;
		}
		//Change last node value to current node
		temp = first.data;
		first.data = last.data;
		last.data = temp;
		return pivot;
	}
	//Perform quick sort in given linked list
	quick_sort(first, last)
	{
		if (first == last)
		{
			return;
		}
		//Find pivot node
		var pivot = this.parition(first, last);
		if (pivot != null && pivot.next != null)
		{
			this.quick_sort(pivot.next, last);
		}
		if (pivot != null && first != pivot)
		{
			this.quick_sort(first, pivot);
		}
	}
}

function main()
{
	var obj = new MyLinkedList();
	//Create linked list
	obj.insert(41);
	obj.insert(5);
	obj.insert(7);
	obj.insert(22);
	obj.insert(28);
	obj.insert(63);
	obj.insert(4);
	obj.insert(8);
	obj.insert(2);
	obj.insert(11);
	process.stdout.write("\n Before Sort ");
	obj.display();
	obj.quick_sort(obj.head, obj.last_node());
	process.stdout.write("\n After Sort ");
	obj.display();
}
main();

Output

 Before Sort
 Linked List : 41 5 7 22 28 63 4 8 2 11
 After Sort
 Linked List : 2 4 5 7 8 11 22 28 41 63
#  Python 3 Program
#  Quicksort on singly linked list

# Node of LinkedList
class Node :
	
	def __init__(self, data) :
		# set node value
		self.data = data
		self.next = None
	
class MyLinkedList :
	
	# Class constructors
	def __init__(self) :
		self.head = None
		self.tail = None
	
	# insert node at last of linke list
	def insert(self, value) :
		# Create a node
		node = Node(value)
		if (self.head == None) :
			# When linked list empty add first node
			self.head = node
			self.tail = node
		else :
			# Add new node at end of linked list
			self.tail.next = node
			self.tail = node
		
	
	# Display linked list nodes
	def display(self) :
		if (self.head != None) :
			print("\n Linked List :", end = "")
			temp = self.head
			while (temp != None) :
				print(" ", temp.data, end = "")
				temp = temp.next
				if (temp == self.head) :
					# avoid loop
					return
				
			
		else :
			print("Empty Linked List", end = "")
		
	
	# Find last node of linked list
	def last_node(self) :
		temp = self.head
		while (temp != None and temp.next != None) :
			temp = temp.next
		
		return temp
	
	# Set of given last node position to its proper position
	def parition(self, first, last) :
		# Get first node of given linked list
		pivot = first
		front = first
		temp = 0
		while (front != None and front != last) :
			if (front.data < last.data) :
				pivot = first
				# Swap node value
				temp = first.data
				first.data = front.data
				front.data = temp
				# Visit to next node
				first = first.next
			
			# Visit to next node
			front = front.next
		
		# Change last node value to current node
		temp = first.data
		first.data = last.data
		last.data = temp
		return pivot
	
	# Perform quick sort in given linked list
	def quick_sort(self, first, last) :
		if (first == last) :
			return
		
		# Find pivot node
		pivot = self.parition(first, last)
		if (pivot != None and pivot.next != None) :
			self.quick_sort(pivot.next, last)
		
		if (pivot != None and first != pivot) :
			self.quick_sort(first, pivot)
		
	

def main() :
	obj = MyLinkedList()
	# Create linked list
	obj.insert(41)
	obj.insert(5)
	obj.insert(7)
	obj.insert(22)
	obj.insert(28)
	obj.insert(63)
	obj.insert(4)
	obj.insert(8)
	obj.insert(2)
	obj.insert(11)
	print("\n Before Sort ", end = "")
	obj.display()
	obj.quick_sort(obj.head, obj.last_node())
	print("\n After Sort ", end = "")
	obj.display()

if __name__ == "__main__": main()

Output

 Before Sort
 Linked List :  41  5  7  22  28  63  4  8  2  11
 After Sort
 Linked List :  2  4  5  7  8  11  22  28  41  63
#  Ruby Program
#  Quicksort on singly linked list

# Node of LinkedList
class Node 

	# Define the accessor and reader of class Node  
	attr_reader :data, :next
	attr_accessor :data, :next

	def initialize(data)
		# set node value
		self.data = data
		self.next = nil
	end
end
class MyLinkedList 

	# Define the accessor and reader of class MyLinkedList  
	attr_reader :head, :tail
	attr_accessor :head, :tail


	
	# Class constructors
	def initialize()
	
		self.head = nil
		self.tail = nil
	end
	# insert node at last of linke list
	def insert(value)
	
		# Create a node
		node = Node.new(value)
		if (self.head == nil)
		
			# When linked list empty add first node
			self.head = node
			self.tail = node
		else
		
			# Add new node at end of linked list
			self.tail.next = node
			self.tail = node
		end
	end
	# Display linked list nodes
	def display()
	
		if (self.head != nil)
		
			print("\n Linked List :")
			temp = self.head
			while (temp != nil)
			
				print(" ", temp.data)
				temp = temp.next
				if (temp == self.head)
				
					# avoid loop
					return
				end
			end
		else
		
			print("Empty Linked List")
		end
	end
	# Find last node of linked list
	def last_node()
	
		temp = self.head
		while (temp != nil && temp.next != nil)
		
			temp = temp.next
		end
		return temp
	end
	# Set of given last node position to its proper position
	def parition(first, last)
	
		# Get first node of given linked list
		pivot = first
		front = first
		temp = 0
		while (front != nil && front != last)
		
			if (front.data < last.data)
			
				pivot = first
				# Swap node value
				temp = first.data
				first.data = front.data
				front.data = temp
				# Visit to next node
				first = first.next
			end
			# Visit to next node
			front = front.next
		end
		# Change last node value to current node
		temp = first.data
		first.data = last.data
		last.data = temp
		return pivot
	end
	# Perform quick sort in given linked list
	def quick_sort(first, last)
	
		if (first == last)
		
			return
		end
		# Find pivot node
		pivot = self.parition(first, last)
		if (pivot != nil && pivot.next != nil)
		
			self.quick_sort(pivot.next, last)
		end
		if (pivot != nil && first != pivot)
		
			self.quick_sort(first, pivot)
		end
	end
end
def main()

	obj = MyLinkedList.new()
	# Create linked list
	obj.insert(41)
	obj.insert(5)
	obj.insert(7)
	obj.insert(22)
	obj.insert(28)
	obj.insert(63)
	obj.insert(4)
	obj.insert(8)
	obj.insert(2)
	obj.insert(11)
	print("\n Before Sort ")
	obj.display()
	obj.quick_sort(obj.head, obj.last_node())
	print("\n After Sort ")
	obj.display()
end
main()

Output

 Before Sort 
 Linked List : 41 5 7 22 28 63 4 8 2 11
 After Sort 
 Linked List : 2 4 5 7 8 11 22 28 41 63
// Scala Program
// Quicksort on singly linked list

//Node of LinkedList
class Node(var data: Int,
	var next: Node)
{
	def this(data: Int)
	{
		this(data, null);
	}
}
class MyLinkedList(var head: Node,
	var tail: Node)
{
	//Class constructors
	def this()
	{
		this(null, null);
	}
	//insert node at last of linke list
	def insert(value: Int): Unit = {
		//Create a node
		var node: Node = new Node(value);
		if (this.head == null)
		{
			//When linked list empty add first node
			this.head = node;
			this.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this.tail.next = node;
			this.tail = node;
		}
	}
	//Display linked list nodes
	def display(): Unit = {
		if (this.head != null)
		{
			print("\n Linked List :");
			var temp: Node = this.head;
			while (temp != null)
			{
				print(" " + temp.data);
				temp = temp.next;
				if (temp == this.head)
				{
					//avoid loop
					return;
				}
			}
		}
		else
		{
			print("Empty Linked List");
		}
	}
	//Find last node of linked list
	def last_node(): Node = {
		var temp: Node = this.head;
		while (temp != null && temp.next != null)
		{
			temp = temp.next;
		}
		return temp;
	}
	//Set of given last node position to its proper position
	def parition(start: Node, last: Node): Node = {
      
		//Get first node of given linked list
      	var first: Node = start;
		var pivot: Node = first;
		var front: Node = first;
		var temp: Int = 0;
		while (front != null && front != last)
		{
			if (front.data < last.data)
			{
				pivot = first;
				//Swap node value
				temp = first.data;
				first.data = front.data;
				front.data = temp;
				//Visit to next node
				first = first.next;
			}
			//Visit to next node
			front = front.next;
		}
		//Change last node value to current node
		temp = first.data;
		first.data = last.data;
		last.data = temp;
		return pivot;
	}
	//Perform quick sort in given linked list
	def quick_sort(first: Node, last: Node): Unit = {
		if (first == last)
		{
			return;
		}
		//Find pivot node
		var pivot: Node = parition(first, last);
		if (pivot != null && pivot.next != null)
		{
			quick_sort(pivot.next, last);
		}
		if (pivot != null && first != pivot)
		{
			quick_sort(first, pivot);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyLinkedList = new MyLinkedList();
		//Create linked list
		obj.insert(41);
		obj.insert(5);
		obj.insert(7);
		obj.insert(22);
		obj.insert(28);
		obj.insert(63);
		obj.insert(4);
		obj.insert(8);
		obj.insert(2);
		obj.insert(11);
		print("\n Before Sort ");
		obj.display();
		obj.quick_sort(obj.head, obj.last_node());
		print("\n After Sort ");
		obj.display();
	}
}

Output

 Before Sort
 Linked List : 41 5 7 22 28 63 4 8 2 11
 After Sort
 Linked List : 2 4 5 7 8 11 22 28 41 63
// Swift Program
// Quicksort on singly linked list
//Node of LinkedList
class Node
{
	var data: Int;
	var next: Node? ;
	init(_ data: Int)
	{
		//set node value
		self.data = data;
		self.next = nil;
	}
}
class MyLinkedList
{
	var head: Node? ;
	var tail: Node? ;
	//Class constructors
	init()
	{
		self.head = nil;
		self.tail = nil;
	}
	//insert node at last of linke list
	func insert(_ value: Int)
	{
		//Create a node
		let node: Node? = Node(value);
		if (self.head == nil)
		{
			//When linked list empty add first node
			self.head = node;
			self.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			self.tail!.next = node;
			self.tail = node;
		}
	}
	//Display linked list nodes
	func display()
	{
		if (self.head != nil)
		{
			print("\n Linked List :", terminator: "");
			var temp: Node? = self.head;
			while (temp != nil)
			{
				print(" ", temp!.data, terminator: "");
				temp = temp!.next;
				if (temp === self.head)
				{
					//avoid loop
					return;
				}
			}
		}
		else
		{
			print("Empty Linked List", terminator: "");
		}
	}
	//Find last node of linked list
	func last_node() -> Node?
	{
		var temp: Node? = self.head;
		while (temp != nil && temp!.next != nil)
		{
			temp = temp!.next;
		}
		return temp;
	}
	//Set of given last node position to its proper position
	func parition(_ start: Node? , _ last : Node? ) -> Node?
	{
		//Get first node of given linked list
      	var first: Node? = start;
		var pivot: Node? = first;
		var front: Node? = first;
		var temp: Int = 0;
		while (front != nil && !(front === last))
		{
			if (front!.data < last!.data)
			{
				pivot = first;
				//Swap node value
				temp = first!.data;
				first!.data = front!.data;
				front!.data = temp;
				//Visit to next node
				first = first!.next;
			}
			//Visit to next node
			front = front!.next;
		}
		//Change last node value to current node
		temp = first!.data;first!.data = last!.data;last!.data = temp;
		return pivot;
	}
	//Perform quick sort in given linked list
	func quick_sort(_ first: Node? , _ last : Node? )
	{
		if (first === last)
		{
			return;
		}
		//Find pivot node
		let pivot: Node? = self.parition(first, last);
		if (pivot != nil && pivot!.next != nil)
		{
			self.quick_sort(pivot!.next, last);
		}
		if (pivot != nil && !(first === pivot))
		{
			self.quick_sort(first, pivot);
		}
	}
}
func main()
{
	let obj: MyLinkedList = MyLinkedList();
	//Create linked list
	obj.insert(41);
	obj.insert(5);
	obj.insert(7);
	obj.insert(22);
	obj.insert(28);
	obj.insert(63);
	obj.insert(4);
	obj.insert(8);
	obj.insert(2);
	obj.insert(11);
	print("\n Before Sort ", terminator: "");
	obj.display();
	obj.quick_sort(obj.head, obj.last_node());
	print("\n After Sort ", terminator: "");
	obj.display();
}
main();

Output

 Before Sort
 Linked List :  41  5  7  22  28  63  4  8  2  11
 After Sort
 Linked List :  2  4  5  7  8  11  22  28  41  63

Resultant Output Explanation

After applying the Quicksort algorithm to the given linked list, the elements are sorted in ascending order. The output of the sorted linked list is as follows:

Linked List: 2 -> 4 -> 5 -> 7 -> 8 -> 11 -> 22 -> 28 -> 41 -> 63

Time Complexity

The time complexity of the Quicksort algorithm on a singly linked list is O(n log n) in the average case and O(n^2) in the worst case. The worst case occurs when the list is already sorted, and the pivot chosen is either the smallest or largest element. The recursive partitioning may lead to a skewed tree, making it less efficient. However, the average case time complexity is quite good and makes it a popular choice for sorting large datasets.

In the given code, the time complexity of partition() is O(n), and the Quicksort algorithm recursively calls itself on smaller partitions. Since the linked list has to be traversed multiple times during the sorting process, the overall time complexity is O(n log n) on average, which is the same as the time complexity of Quicksort on arrays.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment