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
-
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.
-
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
andfront
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 thelast.data
(pivot node value), we swap the data offront
andpivot
nodes, and then movepivot
to the next node. - After the iteration, we swap the data of
pivot
andlast
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.
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