Skip to main content

Quicksort on singly linked list

Here given code implementation process.

// 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
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