# 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 = 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;
};
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;
{
}
else
{
//find last node
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = node;
}
}
}
{
{
return;
}
while (temp != NULL)
{
printf("  %d", temp->data);
temp = temp->next;
}
}
//Find last node of linked list
{
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()
{
printf("\n Before Sort ");
printf("\n After Sort ");
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

class Node
{
public int data;
public Node next;
public Node(int data)
{
//set node value
this.data = data;
this.next = null;
}
}
{
public Node tail;
//Class constructors
{
this.tail = null;
}
//insert node at last of linke list
public void insert(int value)
{
//Create a node
Node node = new Node(value);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
public void display()
{
{
while (temp != null)
{
System.out.print(" " + temp.data);
temp = temp.next;
{
//avoid loop
return;
}
}
}
else
{
}
}
//Find last node of linked list
public Node last_node()
{
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)
{
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();
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

class Node
{
public: int data;
Node * next;
Node(int data)
{
//set node value
this->data = data;
this->next = NULL;
}
};
{
Node * tail;
//Class constructors
{
this->tail = NULL;
}
//insert node at last of linke list
void insert(int value)
{
//Create a node
Node * node = new Node(value);
{
this->tail = node;
}
else
{
this->tail->next = node;
this->tail = node;
}
}
void display()
{
{
cout << "\n Linked List :";
while (temp != NULL)
{
cout << " " << temp->data;
temp = temp->next;
{
//avoid loop
return;
}
}
}
else
{
}
}
//Find last node of linked list
Node * last_node()
{
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()
{
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();
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

class Node
{
public int data;
public Node next;
public Node(int data)
{
//set node value
this.data = data;
this.next = null;
}
}
{
public Node tail;
//Class constructors
{
this.tail = null;
}
//insert node at last of linke list
public void insert(int value)
{
//Create a node
Node node = new Node(value);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
public void display()
{
{
while (temp != null)
{
Console.Write(" " + temp.data);
temp = temp.next;
{
//avoid loop
return;
}
}
}
else
{
}
}
//Find last node of linked list
public Node last_node()
{
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)
{
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();
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

class Node
{
public \$data;
public \$next;

function __construct(\$data)
{
//set node value
\$this->data = \$data;
\$this->next = null;
}
}
{
public \$tail;
//Class constructors
function __construct()
{
\$this->tail = null;
}
//insert node at last of linke list
public	function insert(\$value)
{
//Create a node
\$node = new Node(\$value);
{
\$this->tail = \$node;
}
else
{
\$this->tail->next = \$node;
\$this->tail = \$node;
}
}
public	function display()
{
{
while (\$temp != null)
{
echo " ". \$temp->data;
\$temp = \$temp->next;
{
//avoid loop
return;
}
}
}
else
{
}
}
//Find last node of linked list
public	function last_node()
{
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->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();
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

class Node
{
constructor(data)
{
//set node value
this.data = data;
this.next = null;
}
}
{
//Class constructors
constructor()
{
this.tail = null;
}
//insert node at last of linke list
insert(value)
{
//Create a node
var node = new Node(value);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
display()
{
{
while (temp != null)
{
process.stdout.write(" " + temp.data);
temp = temp.next;
{
//avoid loop
return;
}
}
}
else
{
}
}
//Find last node of linked list
last_node()
{
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()
{
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();
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

class Node :

def __init__(self, data) :
# set node value
self.data = data
self.next = None

# Class constructors
def __init__(self) :
self.tail = None

# insert node at last of linke list
def insert(self, value) :
# Create a node
node = Node(value)
self.tail = node
else :
self.tail.next = node
self.tail = node

def display(self) :
print("\n Linked List :", end = "")
while (temp != None) :
print(" ", temp.data, end = "")
temp = temp.next
# avoid loop
return

else :
print("Empty Linked List", end = "")

# Find last node of linked list
def last_node(self) :
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.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()
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

class Node

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

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

# Class constructors
def initialize()

self.tail = nil
end
# insert node at last of linke list
def insert(value)

# Create a node
node = Node.new(value)

self.tail = node
else

self.tail.next = node
self.tail = node
end
end
def display()

while (temp != nil)

print(" ", temp.data)
temp = temp.next

# avoid loop
return
end
end
else

end
end
# Find last node of linked list
def last_node()

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.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()
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

class Node(var data: Int,
var next: Node)
{
def this(data: Int)
{
this(data, null);
}
}
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);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
def display(): Unit = {
{
while (temp != null)
{
print(" " + temp.data);
temp = temp.next;
{
//avoid loop
return;
}
}
}
else
{
}
}
//Find last node of linked list
def last_node(): Node = {
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 = {
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();
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
class Node
{
var data: Int;
var next: Node? ;
init(_ data: Int)
{
//set node value
self.data = data;
self.next = nil;
}
}
{
var tail: Node? ;
//Class constructors
init()
{
self.tail = nil;
}
//insert node at last of linke list
func insert(_ value: Int)
{
//Create a node
let node: Node? = Node(value);
{
self.tail = node;
}
else
{
self.tail!.next = node;
self.tail = node;
}
}
func display()
{
{
print("\n Linked List :", terminator: "");
while (temp != nil)
{
print(" ", temp!.data, terminator: "");
temp = temp!.next;
{
//avoid loop
return;
}
}
}
else
{
}
}
//Find last node of linked list
func last_node() -> Node?
{
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()
{
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();
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.

## 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.