Skip to main content

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

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment