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;
}
};
void print(Node *head)
{
if (!head)
return;
while (head->next != NULL)
{
cout << head->data << " -> ";
head = head->next;
}
cout << head->data << endl;
}
void swapNodes(Node** headRef, Node* head,Node* min, Node* beforemin)
{
// now the head will be min
*headRef = min;
beforemin->next = head;
// swap both the nodes
Node* temp = min->next;
min->next = head->next;
head->next = temp;
}
void push(Node** headRef, int data)
{
// allocate node
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = (*headRef);
(*headRef) = newNode;
}
Node* selectionSort( Node* head)
{
//run till last node
if (head->next == NULL)
return head;
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.
if (min != head)
swapNodes(&head, head, min, beforeMin);
// call the recursive function
head->next = selectionSort(head->next);
return head;
}
int main(void)
{
Node* head = NULL;
ph(&head, 6);
ph(&head, 8);
ph(&head, 2);
ph(&head, 10);
ph(&head, 12);
cout << "Linked list before sorting: ";
print(head);
Node *tmp = selectionSort(head);
cout << "\nLinked list After sorting: ";
print(tmp);
return 0;
}
You can also try this code with Online C++ Compiler
Run Code
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
Frequently Asked Questions
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 Analysis, Sorting Based Problems, Number Theory, and Dynamic Programing to learn.
Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System 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!