1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Approach
3.1.
Pseudocode For Selection Sort
3.2.
Algorithm for Recursive Selection Sort
3.3.
Implementation in C++
3.3.1.
Time Complexity
3.3.2.
Space Complexity
4.
4.1.
Can we implement selection sort recursively?
4.2.
Which sorting algorithm is best for singly linked lists?
4.3.
What is Recursion?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

## Introduction

A singly linked list is unidirectional, meaning it can only be traversed one way, from head to tail. Linked lists are one of the most essential and often asked data structures in programming contests and technical interviews. This blog tackles a coding task that involves Recursive selection sort for singly linked list (Swapping node links).

## Problem Statement

We will be provided an unsorted linked list in this challenge, and we must recursively sort it using the selection sort algorithm.

### Sample Examples

Input

List 1:

Output

Input

List 2:

Output

Must Read Recursion in Data Structure

## Approach

Firstly, we will look at the pseudocode for selection sort, then we will use recursive selection sort to get the desired sorted singly linked list.

### Pseudocode For Selection Sort

``````Procedure Selectionsort(array,N)
array of items to be sorted
N = size of array
begin traversing
for i = 1 to N-1
begin
set min = i
for j = i+1 to N
begin
if array[j] < array[min] then
min = j;
end if
end for
//swap the minimum element with current element
if minelem != i then
swap array[min] and array[i]
end if
end for
end procedure``````

### Algorithm for Recursive Selection Sort

• Recursive sorting (n-1) times is required, where n is the number of nodes in the list. Because after recursively sorting the list (n-1) times, (n-1) nodes of the list will be in their correct location as per the sorted linked list, we are doing it (n-1) times.

• Each time, we must locate the minimum node to the right of the current node and swap it with the current node.

• Also, remember to save the address of the node immediately preceding the minimum valued node, as this will aid in the swapping of links between nodes.

### Implementation in C++

``````// C++ Program
#include <bits/stdc++.h>
#include<algorithm>
using namespace std;

#define ph push

class Node
{
public:
int data;
Node* next;
Node(int x){
data = x;
next = NULL;
}
};
{
return;

{
cout << head->data << " -> ";
}
}

{
// now the head will be min

// swap both the nodes
Node* temp = min->next;
}

{
// allocate node
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
}

{
//run till last node
Node* min = head, * beforeMin = NULL, * node;

// search for minimum value
for (node = head; node->next != NULL; node = node->next) {
if (node->next->data < min->data) {
min = node->next;
beforeMin = node;
}
}

// Swap the head node with the 'min' node if min is not the same as the current node.

// call the recursive function

}

int main(void)
{

cout << "Linked list before sorting: ";
cout << "\nLinked list After sorting: ";
print(tmp);
return 0;
}``````

Output

``````Linked list before sorting: 12 -> 10 -> 2 -> 8 -> 6
Linked list After sorting: 2 -> 6 -> 8 -> 10 -> 12``````

#### Time Complexity

The time complexity of the above approach is O(n^2), where n is the number of nodes in the linked list.

#### Space Complexity

The space complexity of the above approach is O(n).

Also Read - Selection Sort in C

### Can we implement selection sort recursively?

The recursive implementation of the selection sort algorithm is possible.

### Which sorting algorithm is best for singly linked lists?

When sorting a linked list, merge sort is frequently used. Because of a linked list's slow random-access speed, some algorithms (quicksort) perform badly, while others (heapsort) are impossible.

### What is Recursion?

Recursion is a technique in which a function calls on itself repeatedly, either directly or indirectly, until a certain condition is met or it reaches the function's required stopping point.

## Conclusion

This article extensively discussed the problem of Recursive selection sort for a singly-linked list (Swapping node links) and its time and space complexities.

We hope this blog has helped you enhance your knowledge regarding Linked Lists. After reading about the recursive selection sort for singly linked list (Swapping node links), are you not feeling excited to read more articles on this topic? Don't worry; Coding Ninjas has you covered. See Time Complexity and AnalysisSorting Based ProblemsNumber Theory, and Dynamic Programing to learn.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!