Recursive selection sort for singly linked list
The problem involves implementing recursive selection sort on a singly linked list. Selection sort is a simple sorting algorithm that repeatedly selects the smallest element from an unsorted part of the list and swaps it with the element in the sorted part. The recursive version of selection sort applies the same principle by selecting the minimum element from the unsorted part of the list and placing it in the sorted part. This algorithm has a time complexity of O(n^2) in the worst case.
Problem Statement
You are given a singly linked list, and your task is to sort its elements in ascending order using a recursive implementation of the selection sort algorithm.
Idea to Solve
To solve this problem, you need to implement the following functions:
-
selectionSort
: This function implements the selection sort algorithm recursively. It takes the linked list and the starting node of the unsorted part as parameters. It finds the minimum element in the unsorted part, removes it from the unsorted part, and adds it to the sorted part of the list. The function then calls itself recursively on the remaining unsorted part. -
sortElement
: This function initiates the sorting process. It first checks if the linked list is empty. If not, it initializes the sorted linked list and calls theselectionSort
function to sort the elements.
Pseudocode
- Define
LinkNode
andSingleLL
structures to represent nodes and singly linked lists, respectively. - Implement the
newLinkedList
function to create a new linked list. - Implement the
createNode
function to create a new node with the given data. - Implement the
addNode
function to add a new node at the end of the linked list. - Implement the
display
function to display the elements of the linked list. - Implement the
selectionSort
function to recursively sort the linked list using selection sort.- Base case: If the start node is null, return.
- Find the minimum node in the unsorted part of the list.
- Update the pointers to remove the minimum node from the unsorted part.
- Add the minimum node to the sorted part of the list.
- Recursively call
selectionSort
on the remaining unsorted part.
- Implement the
sortElement
function to initiate the sorting process.- Base case: If the linked list is empty, return.
- Initialize the sorted linked list and call
selectionSort
with the original linked list and the head node as parameters.
- In the
main
function:- Create a new linked list and add elements to it.
- Display the original linked list.
- Call the
sortElement
function to sort the linked list. - Display the sorted linked list.
Program Solution
// C program for
// Recursive selection sort for singly linked list
#include <stdio.h>
#include <stdlib.h>
// Linked List LinkNode
struct LinkNode
{
int data;
struct LinkNode *next;
};
// Singly linked list
struct SingleLL
{
struct LinkNode *head;
struct LinkNode *tail;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
// Create memory of head and tail Nodes
struct SingleLL *sll = (struct SingleLL *) malloc(sizeof(struct SingleLL));
if (sll == NULL)
{
printf("Memory overflow\n");
}
else
{
sll->head = NULL;
sll->tail = NULL;
}
return sll;
}
// Returns the new node of linked list
struct LinkNode * createNode(int data)
{
// Create dynamic node
struct LinkNode *node = (struct LinkNode *) malloc(sizeof(struct LinkNode));
if (node == NULL)
{
printf("Memory overflow to Create LinkNode\n");
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
return node;
}
// Handles the request of adding new node in linked list
void addNode(struct SingleLL *sll, int data)
{
struct LinkNode *node = createNode(data);
if (sll->head == NULL)
{
sll->head = node;
}
else
{
// Append the node at last position
sll->tail->next = node;
}
sll->tail = node;
}
// Display linked list element
void display(struct SingleLL *sll)
{
if (sll->head == NULL)
{
return;
}
struct LinkNode *temp = sll->head;
// iterating linked list elements
while (temp != NULL)
{
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
// Implement selection sort in linked list
void selectionSort(struct SingleLL *sll, struct LinkNode * start)
{
if(start == NULL)
{
// Stop recursion
return;
}
// Define some auxiliary variables
struct LinkNode*auxiliary = start;
struct LinkNode*back = NULL;
struct LinkNode*min = start;
// Find minimum node in linked list
while(auxiliary!=NULL && auxiliary->next != NULL)
{
if(min->data > auxiliary->next->data)
{
min = auxiliary->next;
back = auxiliary;
}
// Visit to next node
auxiliary = auxiliary->next;
}
auxiliary = start;
if(auxiliary==min)
{
// Set new start node
auxiliary = min->next;
}
if(back!=NULL)
{
// Separate the new min element
back->next = min->next;
}
// Set that there is no node after resultant minimum
min->next = NULL;
if(sll->head == NULL)
{
// When have first resultant node
sll->head = min;
}
else
{
// Add resultant node at last position
sll->tail->next = min;
}
// Set new tail of linked list
sll->tail = min;
// Recursive, sort the elements of linked list
selectionSort(sll,auxiliary);
}
// Handles the request of sorting linked list element
void sortElement(struct SingleLL *sll)
{
if(sll->head==NULL)
{
return;
}
struct LinkNode*temp = sll->head;
sll->head = NULL;
selectionSort(sll,temp);
}
int main(int argc, char const *argv[])
{
struct SingleLL *sll = newLinkedList();
// 1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
addNode(sll, 1);
addNode(sll, 17);
addNode(sll, -4);
addNode(sll, 16);
addNode(sll, -5);
addNode(sll, 29);
addNode(sll, 7);
addNode(sll, 39);
addNode(sll, 23);
printf("\n Before Sort Linked List : \n");
display(sll);
// Sort element
sortElement(sll);
printf("\n After Sort Linked List : \n");
display(sll);
return 0;
}
input
Before Sort Linked List :
1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
After Sort Linked List :
-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
/*
Java Program for
Recursive selection sort for singly linked list
*/
// Linked list node
class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public LinkNode head;
public LinkNode tail;
public SingleLL()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
public void display()
{
if (this.head == null)
{
System.out.println("\n Empty linked list");
return;
}
LinkNode temp = this.head;
//iterating linked list elements
while (temp != null)
{
System.out.print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
System.out.print(" NULL\n");
}
// Implement selection sort in linked list
public void selectionSort(LinkNode start)
{
if (start == null)
{
// Stop recursion
return;
}
// Define some auxiliary variables
LinkNode auxiliary = start;
LinkNode back = null;
LinkNode min = start;
// Find minimum node in linked list
while (auxiliary != null && auxiliary.next != null)
{
if (min.data > auxiliary.next.data)
{
min = auxiliary.next;
back = auxiliary;
}
// Visit to next node
auxiliary = auxiliary.next;
}
auxiliary = start;
if (auxiliary == min)
{
// Set new start node
auxiliary = min.next;
}
if (back != null)
{
// Separate the new min element
back.next = min.next;
}
// Set that there is no node after resultant minimum
min.next = null;
if (this.head == null)
{
// When have first resultant node
this.head = min;
}
else
{
// Add resultant node at last position
this.tail.next = min;
}
// Set new tail of linked list
this.tail = min;
// Recursive, sort the elements of linked list
selectionSort(auxiliary);
}
// Handles the request of sorting linked list element
public void sortElement()
{
if (this.head == null)
{
return;
}
LinkNode temp = this.head;
this.head = null;
selectionSort(temp);
}
public static void main(String[] args)
{
SingleLL sll = new SingleLL();
// Construct linked list
sll.addNode(1);
sll.addNode(17);
sll.addNode(-4);
sll.addNode(16);
sll.addNode(-5);
sll.addNode(29);
sll.addNode(7);
sll.addNode(39);
sll.addNode(23);
System.out.print("\n Before Sort Linked List : \n");
// 1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
sll.display();
// Sort element
sll.sortElement();
System.out.print("\n After Sort Linked List : \n");
// -5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
sll.display();
}
}
input
Before Sort Linked List :
1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
After Sort Linked List :
-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Recursive selection sort for singly linked list
*/
// Linked list node
class LinkNode
{
public:
int data;
LinkNode *next;
LinkNode(int data)
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
public:
LinkNode *head;
LinkNode *tail;
SingleLL()
{
this->head = NULL;
this->tail = NULL;
}
// Add new Node at end of linked list
void addNode(int data)
{
LinkNode *node = new LinkNode(data);
if (this->head == NULL)
{
this->head = node;
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
// Display linked list element
void display()
{
if (this->head == NULL)
{
cout << "\n Empty linked list" << endl;
return;
}
LinkNode *temp = this->head;
//iterating linked list elements
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL\n";
}
// Implement selection sort in linked list
void selectionSort(LinkNode *start)
{
if (start == NULL)
{
// Stop recursion
return;
}
// Define some auxiliary variables
LinkNode *auxiliary = start;
LinkNode *back = NULL;
LinkNode *min = start;
// Find minimum node in linked list
while (auxiliary != NULL && auxiliary->next != NULL)
{
if (min->data > auxiliary->next->data)
{
min = auxiliary->next;
back = auxiliary;
}
// Visit to next node
auxiliary = auxiliary->next;
}
auxiliary = start;
if (auxiliary == min)
{
// Set new start node
auxiliary = min->next;
}
if (back != NULL)
{
// Separate the new min element
back->next = min->next;
}
// Set that there is no node after resultant minimum
min->next = NULL;
if (this->head == NULL)
{
// When have first resultant node
this->head = min;
}
else
{
// Add resultant node at last position
this->tail->next = min;
}
// Set new tail of linked list
this->tail = min;
// Recursive, sort the elements of linked list
this->selectionSort(auxiliary);
}
// Handles the request of sorting linked list element
void sortElement()
{
if (this->head == NULL)
{
return;
}
LinkNode *temp = this->head;
this->head = NULL;
this->selectionSort(temp);
}
};
int main()
{
SingleLL *sll = new SingleLL();
// Construct linked list
sll->addNode(1);
sll->addNode(17);
sll->addNode(-4);
sll->addNode(16);
sll->addNode(-5);
sll->addNode(29);
sll->addNode(7);
sll->addNode(39);
sll->addNode(23);
cout << "\n Before Sort Linked List : \n";
// 1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
sll->display();
// Sort element
sll->sortElement();
cout << "\n After Sort Linked List : \n";
// -5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
sll->display();
return 0;
}
input
Before Sort Linked List :
1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
After Sort Linked List :
-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
// Include namespace system
using System;
/*
Csharp Program for
Recursive selection sort for singly linked list
*/
// Linked list node
public class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public LinkNode head;
public LinkNode tail;
public SingleLL()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
public void display()
{
if (this.head == null)
{
Console.WriteLine("\n Empty linked list");
return;
}
LinkNode temp = this.head;
//iterating linked list elements
while (temp != null)
{
Console.Write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
Console.Write(" NULL\n");
}
// Implement selection sort in linked list
public void selectionSort(LinkNode start)
{
if (start == null)
{
// Stop recursion
return;
}
// Define some auxiliary variables
LinkNode auxiliary = start;
LinkNode back = null;
LinkNode min = start;
// Find minimum node in linked list
while (auxiliary != null && auxiliary.next != null)
{
if (min.data > auxiliary.next.data)
{
min = auxiliary.next;
back = auxiliary;
}
// Visit to next node
auxiliary = auxiliary.next;
}
auxiliary = start;
if (auxiliary == min)
{
// Set new start node
auxiliary = min.next;
}
if (back != null)
{
// Separate the new min element
back.next = min.next;
}
// Set that there is no node after resultant minimum
min.next = null;
if (this.head == null)
{
// When have first resultant node
this.head = min;
}
else
{
// Add resultant node at last position
this.tail.next = min;
}
// Set new tail of linked list
this.tail = min;
// Recursive, sort the elements of linked list
this.selectionSort(auxiliary);
}
// Handles the request of sorting linked list element
public void sortElement()
{
if (this.head == null)
{
return;
}
LinkNode temp = this.head;
this.head = null;
this.selectionSort(temp);
}
public static void Main(String[] args)
{
SingleLL sll = new SingleLL();
// Construct linked list
sll.addNode(1);
sll.addNode(17);
sll.addNode(-4);
sll.addNode(16);
sll.addNode(-5);
sll.addNode(29);
sll.addNode(7);
sll.addNode(39);
sll.addNode(23);
Console.Write("\n Before Sort Linked List : \n");
// 1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
sll.display();
// Sort element
sll.sortElement();
Console.Write("\n After Sort Linked List : \n");
// -5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
sll.display();
}
}
input
Before Sort Linked List :
1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
After Sort Linked List :
-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
<?php
/*
Php Program for
Recursive selection sort for singly linked list
*/
// Linked list node
class LinkNode
{
public $data;
public $next;
public function __construct($data)
{
$this->data = $data;
$this->next = NULL;
}
}
class SingleLL
{
public $head;
public $tail;
public function __construct()
{
$this->head = NULL;
$this->tail = NULL;
}
// Add new Node at end of linked list
public function addNode($data)
{
$node = new LinkNode($data);
if ($this->head == NULL)
{
$this->head = $node;
}
else
{
// Append the node at last position
$this->tail->next = $node;
}
$this->tail = $node;
}
// Display linked list element
public function display()
{
if ($this->head == NULL)
{
echo("\n Empty linked list".
"\n");
return;
}
$temp = $this->head;
//iterating linked list elements
while ($temp != NULL)
{
echo(" ".$temp->data.
" →");
// Visit to next node
$temp = $temp->next;
}
echo(" NULL\n");
}
// Implement selection sort in linked list
public function selectionSort($start)
{
if ($start == NULL)
{
// Stop recursion
return;
}
// Define some auxiliary variables
$auxiliary = $start;
$back = NULL;
$min = $start;
// Find minimum node in linked list
while ($auxiliary != NULL && $auxiliary->next != NULL)
{
if ($min->data > $auxiliary->next->data)
{
$min = $auxiliary->next;
$back = $auxiliary;
}
// Visit to next node
$auxiliary = $auxiliary->next;
}
$auxiliary = $start;
if ($auxiliary == $min)
{
// Set new start node
$auxiliary = $min->next;
}
if ($back != NULL)
{
// Separate the new min element
$back->next = $min->next;
}
// Set that there is no node after resultant minimum
$min->next = NULL;
if ($this->head == NULL)
{
// When have first resultant node
$this->head = $min;
}
else
{
// Add resultant node at last position
$this->tail->next = $min;
}
// Set new tail of linked list
$this->tail = $min;
// Recursive, sort the elements of linked list
$this->selectionSort($auxiliary);
}
// Handles the request of sorting linked list element
public function sortElement()
{
if ($this->head == NULL)
{
return;
}
$temp = $this->head;
$this->head = NULL;
$this->selectionSort($temp);
}
}
function main()
{
$sll = new SingleLL();
// Construct linked list
$sll->addNode(1);
$sll->addNode(17);
$sll->addNode(-4);
$sll->addNode(16);
$sll->addNode(-5);
$sll->addNode(29);
$sll->addNode(7);
$sll->addNode(39);
$sll->addNode(23);
echo("\n Before Sort Linked List : \n");
// 1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
$sll->display();
// Sort element
$sll->sortElement();
echo("\n After Sort Linked List : \n");
// -5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
$sll->display();
}
main();
input
Before Sort Linked List :
1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
After Sort Linked List :
-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
/*
Node JS Program for
Recursive selection sort for singly linked list
*/
// Linked list node
class LinkNode
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
addNode(data)
{
var node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
display()
{
if (this.head == null)
{
console.log("\n Empty linked list");
return;
}
var temp = this.head;
//iterating linked list elements
while (temp != null)
{
process.stdout.write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
process.stdout.write(" NULL\n");
}
// Implement selection sort in linked list
selectionSort(start)
{
if (start == null)
{
// Stop recursion
return;
}
// Define some auxiliary variables
var auxiliary = start;
var back = null;
var min = start;
// Find minimum node in linked list
while (auxiliary != null && auxiliary.next != null)
{
if (min.data > auxiliary.next.data)
{
min = auxiliary.next;
back = auxiliary;
}
// Visit to next node
auxiliary = auxiliary.next;
}
auxiliary = start;
if (auxiliary == min)
{
// Set new start node
auxiliary = min.next;
}
if (back != null)
{
// Separate the new min element
back.next = min.next;
}
// Set that there is no node after resultant minimum
min.next = null;
if (this.head == null)
{
// When have first resultant node
this.head = min;
}
else
{
// Add resultant node at last position
this.tail.next = min;
}
// Set new tail of linked list
this.tail = min;
// Recursive, sort the elements of linked list
this.selectionSort(auxiliary);
}
// Handles the request of sorting linked list element
sortElement()
{
if (this.head == null)
{
return;
}
var temp = this.head;
this.head = null;
this.selectionSort(temp);
}
}
function main()
{
var sll = new SingleLL();
// Construct linked list
sll.addNode(1);
sll.addNode(17);
sll.addNode(-4);
sll.addNode(16);
sll.addNode(-5);
sll.addNode(29);
sll.addNode(7);
sll.addNode(39);
sll.addNode(23);
process.stdout.write("\n Before Sort Linked List : \n");
// 1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
sll.display();
// Sort element
sll.sortElement();
process.stdout.write("\n After Sort Linked List : \n");
// -5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
sll.display();
}
main();
input
Before Sort Linked List :
1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
After Sort Linked List :
-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
# Python 3 Program for
# Recursive selection sort for singly linked list
# Linked list node
class LinkNode :
def __init__(self, data) :
self.data = data
self.next = None
class SingleLL :
def __init__(self) :
self.head = None
self.tail = None
# Add new Node at end of linked list
def addNode(self, data) :
node = LinkNode(data)
if (self.head == None) :
self.head = node
else :
# Append the node at last position
self.tail.next = node
self.tail = node
# Display linked list element
def display(self) :
if (self.head == None) :
print("\n Empty linked list")
return
temp = self.head
# iterating linked list elements
while (temp != None) :
print("", temp.data ,"→", end = "")
# Visit to next node
temp = temp.next
print(" NULL")
# Implement selection sort in linked list
def selectionSort(self, start) :
if (start == None) :
# Stop recursion
return
# Define some auxiliary variables
auxiliary = start
back = None
min = start
# Find minimum node in linked list
while (auxiliary != None and auxiliary.next != None) :
if (min.data > auxiliary.next.data) :
min = auxiliary.next
back = auxiliary
# Visit to next node
auxiliary = auxiliary.next
auxiliary = start
if (auxiliary == min) :
# Set new start node
auxiliary = min.next
if (back != None) :
# Separate the new min element
back.next = min.next
# Set that there is no node after resultant minimum
min.next = None
if (self.head == None) :
# When have first resultant node
self.head = min
else :
# Add resultant node at last position
self.tail.next = min
# Set new tail of linked list
self.tail = min
# Recursive, sort the elements of linked list
self.selectionSort(auxiliary)
# Handles the request of sorting linked list element
def sortElement(self) :
if (self.head == None) :
return
temp = self.head
self.head = None
self.selectionSort(temp)
def main() :
sll = SingleLL()
# Construct linked list
sll.addNode(1)
sll.addNode(17)
sll.addNode(-4)
sll.addNode(16)
sll.addNode(-5)
sll.addNode(29)
sll.addNode(7)
sll.addNode(39)
sll.addNode(23)
print("\n Before Sort Linked List : ")
# 1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
sll.display()
# Sort element
sll.sortElement()
print("\n After Sort Linked List : ")
# -5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
sll.display()
if __name__ == "__main__": main()
input
Before Sort Linked List :
1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
After Sort Linked List :
-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
# Ruby Program for
# Recursive selection sort for singly linked list
# Linked list node
class LinkNode
# Define the accessor and reader of class LinkNode
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end
end
class SingleLL
# Define the accessor and reader of class SingleLL
attr_reader :head, :tail
attr_accessor :head, :tail
def initialize()
self.head = nil
self.tail = nil
end
# Add new Node at end of linked list
def addNode(data)
node = LinkNode.new(data)
if (self.head == nil)
self.head = node
else
# Append the node at last position
self.tail.next = node
end
self.tail = node
end
# Display linked list element
def display()
if (self.head == nil)
print("\n Empty linked list", "\n")
return
end
temp = self.head
# iterating linked list elements
while (temp != nil)
print(" ", temp.data ," →")
# Visit to next node
temp = temp.next
end
print(" NULL\n")
end
# Implement selection sort in linked list
def selectionSort(start)
if (start == nil)
# Stop recursion
return
end
# Define some auxiliary variables
auxiliary = start
back = nil
min = start
# Find minimum node in linked list
while (auxiliary != nil && auxiliary.next != nil)
if (min.data > auxiliary.next.data)
min = auxiliary.next
back = auxiliary
end
# Visit to next node
auxiliary = auxiliary.next
end
auxiliary = start
if (auxiliary == min)
# Set new start node
auxiliary = min.next
end
if (back != nil)
# Separate the new min element
back.next = min.next
end
# Set that there is no node after resultant minimum
min.next = nil
if (self.head == nil)
# When have first resultant node
self.head = min
else
# Add resultant node at last position
self.tail.next = min
end
# Set new tail of linked list
self.tail = min
# Recursive, sort the elements of linked list
self.selectionSort(auxiliary)
end
# Handles the request of sorting linked list element
def sortElement()
if (self.head == nil)
return
end
temp = self.head
self.head = nil
self.selectionSort(temp)
end
end
def main()
sll = SingleLL.new()
# Construct linked list
sll.addNode(1)
sll.addNode(17)
sll.addNode(-4)
sll.addNode(16)
sll.addNode(-5)
sll.addNode(29)
sll.addNode(7)
sll.addNode(39)
sll.addNode(23)
print("\n Before Sort Linked List : \n")
# 1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
sll.display()
# Sort element
sll.sortElement()
print("\n After Sort Linked List : \n")
# -5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
sll.display()
end
main()
input
Before Sort Linked List :
1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
After Sort Linked List :
-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
/*
Scala Program for
Recursive selection sort for singly linked list
*/
// Linked list node
class LinkNode(var data: Int , var next: LinkNode)
{
def this(data: Int)
{
this(data,null);
}
}
class SingleLL(var head: LinkNode , var tail: LinkNode)
{
def this()
{
this(null,null);
}
// Add new Node at end of linked list
def addNode(data: Int): Unit = {
var node: LinkNode = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
def display(): Unit = {
if (this.head == null)
{
println("\n Empty linked list");
return;
}
var temp: LinkNode = this.head;
//iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Implement selection sort in linked list
def selectionSort(start: LinkNode): Unit = {
if (start == null)
{
// Stop recursion
return;
}
// Define some auxiliary variables
var auxiliary: LinkNode = start;
var back: LinkNode = null;
var min: LinkNode = start;
// Find minimum node in linked list
while (auxiliary != null && auxiliary.next != null)
{
if (min.data > auxiliary.next.data)
{
min = auxiliary.next;
back = auxiliary;
}
// Visit to next node
auxiliary = auxiliary.next;
}
auxiliary = start;
if (auxiliary == min)
{
// Set new start node
auxiliary = min.next;
}
if (back != null)
{
// Separate the new min element
back.next = min.next;
}
// Set that there is no node after resultant minimum
min.next = null;
if (this.head == null)
{
// When have first resultant node
this.head = min;
}
else
{
// Add resultant node at last position
this.tail.next = min;
}
// Set new tail of linked list
this.tail = min;
// Recursive, sort the elements of linked list
selectionSort(auxiliary);
}
// Handles the request of sorting linked list element
def sortElement(): Unit = {
if (this.head == null)
{
return;
}
var temp: LinkNode = this.head;
this.head = null;
selectionSort(temp);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var sll: SingleLL = new SingleLL();
// Construct linked list
sll.addNode(1);
sll.addNode(17);
sll.addNode(-4);
sll.addNode(16);
sll.addNode(-5);
sll.addNode(29);
sll.addNode(7);
sll.addNode(39);
sll.addNode(23);
print("\n Before Sort Linked List : \n");
// 1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
sll.display();
// Sort element
sll.sortElement();
print("\n After Sort Linked List : \n");
// -5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
sll.display();
}
}
input
Before Sort Linked List :
1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
After Sort Linked List :
-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
/*
Swift 4 Program for
Recursive selection sort for singly linked list
*/
// Linked list node
class LinkNode
{
var data: Int;
var next: LinkNode? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
var head: LinkNode? ;
var tail: LinkNode? ;
init()
{
self.head = nil;
self.tail = nil;
}
// Add new Node at end of linked list
func addNode(_ data: Int)
{
let node: LinkNode = LinkNode(data);
if (self.head == nil)
{
self.head = node;
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
// Display linked list element
func display()
{
if (self.head == nil)
{
print("\n Empty linked list");
return;
}
var temp: LinkNode? = self.head;
//iterating linked list elements
while (temp != nil)
{
print("", temp!.data ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
// Implement selection sort in linked list
func selectionSort(_ start: LinkNode? )
{
if (start == nil)
{
// Stop recursion
return;
}
// Define some auxiliary variables
var auxiliary: LinkNode? = start;
var back: LinkNode? = nil;
var min: LinkNode? = start;
// Find minimum node in linked list
while (auxiliary != nil && auxiliary!.next != nil)
{
if (min!.data > auxiliary!.next!.data)
{
min = auxiliary!.next;
back = auxiliary;
}
// Visit to next node
auxiliary = auxiliary!.next;
}
auxiliary = start;
if (auxiliary === min)
{
// Set new start node
auxiliary = min!.next;
}
if (back != nil)
{
// Separate the new min element
back!.next = min!.next;
}
// Set that there is no node after resultant minimum
min!.next = nil;
if (self.head == nil)
{
// When have first resultant node
self.head = min;
}
else
{
// Add resultant node at last position
self.tail!.next = min;
}
// Set new tail of linked list
self.tail = min;
// Recursive, sort the elements of linked list
self.selectionSort(auxiliary);
}
// Handles the request of sorting linked list element
func sortElement()
{
if (self.head == nil)
{
return;
}
let temp: LinkNode? = self.head;
self.head = nil;
self.selectionSort(temp);
}
}
func main()
{
let sll: SingleLL = SingleLL();
// Construct linked list
sll.addNode(1);
sll.addNode(17);
sll.addNode(-4);
sll.addNode(16);
sll.addNode(-5);
sll.addNode(29);
sll.addNode(7);
sll.addNode(39);
sll.addNode(23);
print("\n Before Sort Linked List : ");
// 1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
sll.display();
// Sort element
sll.sortElement();
print("\n After Sort Linked List : ");
// -5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
sll.display();
}
main();
input
Before Sort Linked List :
1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
After Sort Linked List :
-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
/*
Kotlin Program for
Recursive selection sort for singly linked list
*/
// Linked list node
class LinkNode
{
var data: Int;
var next: LinkNode ? ;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
var head: LinkNode ? ;
var tail: LinkNode ? ;
constructor()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
fun addNode(data: Int): Unit
{
val node: LinkNode = LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
// Display linked list element
fun display(): Unit
{
if (this.head == null)
{
println("\n Empty linked list");
return;
}
var temp: LinkNode ? = this.head;
//iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Implement selection sort in linked list
fun selectionSort(start: LinkNode ? ): Unit
{
if (start == null)
{
// Stop recursion
return;
}
// Define some auxiliary variables
var auxiliary: LinkNode ? = start;
var back: LinkNode ? = null;
var min: LinkNode ? = start;
// Find minimum node in linked list
while (auxiliary != null && auxiliary.next != null)
{
if (min!!.data > auxiliary.next!!.data)
{
min = auxiliary.next;
back = auxiliary;
}
// Visit to next node
auxiliary = auxiliary.next;
}
auxiliary = start;
if (auxiliary == min)
{
// Set new start node
auxiliary = min.next;
}
if (back != null)
{
// Separate the new min element
back.next = min?.next;
}
// Set that there is no node after resultant minimum
min?.next = null;
if (this.head == null)
{
// When have first resultant node
this.head = min;
}
else
{
// Add resultant node at last position
this.tail?.next = min;
}
// Set new tail of linked list
this.tail = min;
// Recursive, sort the elements of linked list
this.selectionSort(auxiliary);
}
// Handles the request of sorting linked list element
fun sortElement(): Unit
{
if (this.head == null)
{
return;
}
var temp: LinkNode ? = this.head;
this.head = null;
this.selectionSort(temp);
}
}
fun main(args: Array < String > ): Unit
{
val sll: SingleLL = SingleLL();
// Construct linked list
sll.addNode(1);
sll.addNode(17);
sll.addNode(-4);
sll.addNode(16);
sll.addNode(-5);
sll.addNode(29);
sll.addNode(7);
sll.addNode(39);
sll.addNode(23);
print("\n Before Sort Linked List : \n");
// 1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
sll.display();
// Sort element
sll.sortElement();
print("\n After Sort Linked List : \n");
// -5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
sll.display();
}
input
Before Sort Linked List :
1 → 17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL
After Sort Linked List :
-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
Time Complexity
The recursive selection sort algorithm has a time complexity of O(n^2) in the worst case, where 'n' is the number of elements in the linked list. This is because for each element, the algorithm needs to traverse the remaining unsorted part of the list to find the minimum element.
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