Posted on by Kalkicode
Code Recursion

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

1. `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.

2. `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 the `selectionSort` function to sort the elements.

## Pseudocode

1. Define `LinkNode` and `SingleLL` structures to represent nodes and singly linked lists, respectively.
2. Implement the `newLinkedList` function to create a new linked list.
3. Implement the `createNode` function to create a new node with the given data.
4. Implement the `addNode` function to add a new node at the end of the linked list.
5. Implement the `display` function to display the elements of the linked list.
6. 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.
7. 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.
8. In the `main` function:
• 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>

{
int data;
};
struct SingleLL
{
};
// Returns the new linked list
{
// 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->tail = NULL;
}
return sll;
}

// Returns the new node of linked list
{

// Create dynamic node

if (node == NULL)
{
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
return node;
}

void addNode(struct SingleLL *sll, int data)
{

{
}
else
{
// Append the node at last position
sll->tail->next = node;
}
sll->tail = node;
}
void display(struct SingleLL *sll)
{
{
return;
}
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

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

{
// When have first resultant node
}
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)
{
{

return;
}

selectionSort(sll,temp);

}
int main(int argc, char const *argv[])
{

//  1 →  17 → -4 → 16 → -5 → 29 → 7 → 39 → 23 → NULL

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

-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL``````
``````/*
Java Program for
Recursive selection sort for singly linked list
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
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
{
if (start == null)
{
// Stop recursion
return;
}
// Define some auxiliary variables
// 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;
{
// When have first resultant node
}
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()
{
{
return;
}
selectionSort(temp);
}
public static void main(String[] args)
{
SingleLL sll = new SingleLL();
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

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

{
public:
int data;
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
public:
SingleLL()
{
this->tail = NULL;
}
{
{
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
void display()
{
{
cout << "\n Empty linked list" << endl;
return;
}
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL\n";
}
// Implement selection sort in linked list
{
if (start == NULL)
{
// Stop recursion
return;
}
// Define some auxiliary variables
// 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;
{
// When have first resultant node
}
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()
{
{
return;
}
this->selectionSort(temp);
}
};
int main()
{
SingleLL *sll = new SingleLL();
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

-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
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
while (temp != null)
{
Console.Write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
Console.Write(" NULL\n");
}
// Implement selection sort in linked list
{
if (start == null)
{
// Stop recursion
return;
}
// Define some auxiliary variables
// 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;
{
// When have first resultant node
}
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()
{
{
return;
}
this.selectionSort(temp);
}
public static void Main(String[] args)
{
SingleLL sll = new SingleLL();
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

-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL``````
``````<?php
/*
Php Program for
Recursive selection sort for singly linked list
*/
{
public \$data;
public \$next;
public	function __construct(\$data)
{
\$this->data = \$data;
\$this->next = NULL;
}
}
class SingleLL
{
public \$tail;
public	function __construct()
{
\$this->tail = NULL;
}
{
{
}
else
{
// Append the node at last position
\$this->tail->next = \$node;
}
\$this->tail = \$node;
}
public	function display()
{
{
"\n");
return;
}
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;
{
// When have first resultant node
}
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()
{
{
return;
}
\$this->selectionSort(\$temp);
}
}

function main()
{
\$sll = new SingleLL();
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

-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL``````
``````/*
Node JS Program for
Recursive selection sort for singly linked list
*/
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
display()
{
{
return;
}
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;
{
// When have first resultant node
}
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()
{
{
return;
}
this.selectionSort(temp);
}
}

function main()
{
var sll = new SingleLL();
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

-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL``````
``````#  Python 3 Program for
#  Recursive selection sort for singly linked list

def __init__(self, data) :
self.data = data
self.next = None

class SingleLL :
def __init__(self) :
self.tail = None

else :
#  Append the node at last position
self.tail.next = node

self.tail = node

def display(self) :
return

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
#  When have first resultant node
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) :
return

self.selectionSort(temp)

def main() :
sll = SingleLL()
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

-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL``````
``````#  Ruby Program for
#  Recursive selection sort for singly linked list

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
def initialize()
self.tail = nil
end

else
#  Append the node at last position
self.tail.next = node
end

self.tail = node
end

def display()
return
end

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
#  When have first resultant node
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()
return
end

self.selectionSort(temp)
end

end

def main()
sll = SingleLL.new()
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

-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL
``````
``````/*
Scala Program for
Recursive selection sort for singly linked list
*/
{
def this(data: Int)
{
this(data,null);
}
}
{
def this()
{
this(null,null);
}
def addNode(data: Int): Unit = {
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
def display(): Unit = {
{
return;
}
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
// 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;
{
// When have first resultant node
}
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 = {
{
return;
}
selectionSort(temp);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var sll: SingleLL = new SingleLL();
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

-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL``````
``````/*
Swift 4 Program for
Recursive selection sort for singly linked list
*/
{
var data: Int;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
init()
{
self.tail = nil;
}
{
{
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
func display()
{
{
return;
}
while (temp  != nil)
{
print("", temp!.data ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
// Implement selection sort in linked list
{
if (start == nil)
{
// Stop recursion
return;
}
// Define some auxiliary variables
// 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;
{
// When have first resultant node
}
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()
{
{
return;
}
self.selectionSort(temp);
}
}
func main()
{
let sll: SingleLL = SingleLL();
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

-5 → -4 → 1 → 7 → 16 → 17 → 23 → 29 → 39 → NULL``````
``````/*
Kotlin Program for
Recursive selection sort for singly linked list
*/
{
var data: Int;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
fun display(): Unit
{
{
return;
}
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;
{
// When have first resultant node
}
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
{
{
return;
}
this.selectionSort(temp);
}
}
fun main(args: Array < String > ): Unit
{
val sll: SingleLL = SingleLL();
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

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

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

Categories
Relative Post