# Iterative Selection Sort For Linked List ### Problem Statement

In this problem we are given the head of a linked list denoting the whole linked list, we have to iteratively sort the linked list using selection sort. Suppose we have a linked list represented as – Then the sorted linked list is given as – Selection sort on the Linked list works in a similar way as it does on arrays but here instead of accessing the elements directly, we will be dealing with the links. Most of the Linked List problems are based on manipulation of the links.

### Approach & Algorithm

The idea is to Iterate over the given Linked list N times where N is the number of elements in the Linked list. In every iteration of the algorithm, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray of the Linked list.
Now we have to perform a similar swapping operation, which is done in Linked list in 2 ways –

• By swapping the data parts of the nodes.
• By swapping the complete nodes.

We will be using here the second way to swap the nodes by manipulating the links. While we do the swapping of the link parts of two nodes, four cases arise:

• When nodes are adjacent and the first node is the head node.
• Nodes can be adjacent and the first node isn’t the head node.
• Nodes might not be adjacent and the first node is the head node.
• Nodes might not be adjacent and the first node isn’t the head node.

### Iterative Selection Sort For Linked List

```#include
using namespace std;
struct Node {
int data;
Node* next;
};
Node* newNode(int val)
{
Node* temp = new Node;
temp->data = val;
temp->next = NULL;
return temp;
}
{
Node *x, *y, *z, *w, *s;
x = y = head;
while (y->next) {
z = w = y->next;
while (w) {
if (y->data > w->data) {
if (y->next == w) {
if (y == head) {
y->next = w->next;
w->next = y;
s = y;
y = w;
w = s;
z = w;
w = w->next;
}
else {
y->next = w->next;
w->next = y;
x->next = w;
s = y;
y = w;
w = s;
z = w;
w = w->next;
}
}
else {
if (y == head) {
s = y->next;
y->next = w->next;
w->next = s;
z->next = y;
s = y;
y = w;
w = s;
z = w;
w = w->next;
}
else {
s = y->next;
y->next = w->next;
w->next = s;
z->next = y;
x->next = w;
s = y;
y = w;
w = s;
z = w;
w = w->next;
}
}
}
else {
z = w;
w = w->next;
}
}

x = y;
y = y->next;
}

}
{
cout << head->data << "->";
}
}
int main()
{
Node* head = newNode(5);
return 0;
}
```
```#include
#include

struct Node {
int data;
struct Node* next;
};
struct Node* newNode(int val)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = val;
temp->next = NULL;
return temp;
}
struct Node* selectionsortfunction(struct Node* head)
{
struct Node *x, *y, *z, *w, *s;
x = y = head;
while (y->next) {
z = w = y->next;
while (w) {
if (y->data > w->data) {
if (y->next == w) {
if (y == head) {
y->next = w->next;
w->next = y;
s = y;
y = w;
w = s;
z = w;
w = w->next;
}
else {
y->next = w->next;
w->next = y;
x->next = w;
s = y;
y = w;
w = s;
z = w;
w = w->next;
}
}
else {
if (y == head) {
s = y->next;
y->next = w->next;
w->next = s;
z->next = y;
s = y;
y = w;
w = s;
z = w;
w = w->next;
}
else {
s = y->next;
y->next = w->next;
w->next = s;
z->next = y;
x->next = w;
s = y;
y = w;
w = s;
z = w;
w = w->next;
}
}
}
else {
z = w;
w = w->next;
}
}
x = y;
y = y->next;
}

}
void show(struct Node* head)
{
}
}
int main()
{
struct Node* head = newNode(5);
return 0;
}

```
```
class IterativeSort
{
static class Node
{
int data;
Node next;
};
static Node newNode(int val)
{
Node temp = new Node();

temp.data = val;

temp.next = null;

return temp;
}

/* Function to sort a linked list using selection
sort algorithm by swapping the next pointers */
static Node selectionSort(Node head)
{
Node a, b, c, d, r;
a = b = head;
// While b is not the last node
while (b.next != null)
{
c = d = b.next;
// While d is pointing to a valid node
while (d != null)
{
if (b.data > d.data)
{
// If d appears immediately after b
if (b.next == d)
{
if (b == head)
{
b.next = d.next;
d.next = b;

// Swap b and d pointers
r = b;
b = d;
d = r;

c = d;

// Update the head
d = d.next;
}
// Case 2: b is not the head of the linked list
else
{
b.next = d.next;
d.next = b;
a.next = d;

// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;

d = d.next;
}
}
/* If b and d have some non-zero number of nodes in between them */
else
{
// Case 3: b is the head of the linked list
if (b == head)
{
// Swap b.next and d.next
r = b.next;
b.next = d.next;
d.next = r;
c.next = b;

// Swap b and d pointers
r = b;
b = d;
d = r;

c = d;

// as it is already in order
d = d.next;

// Update the head
}
// Case 4: b is not the head of the linked list
else
{
// Swap b.next and d.next
r = b.next;
b.next = d.next;
d.next = r;
c.next = b;
a.next = d;

// Swap b and d pointers
r = b;
b = d;
d = r;

c = d;

// as it is already in order
d = d.next;
}
}
}
else
{
c = d;
d = d.next;
}
}
a = b;
b = b.next;
}
}
static void printList(Node head)
{
while (head != null) {
System.out.print(head.data + " ");
}
}

// Driver Code
public static void main(String args[])
{
Node head = newNode(5);

}
}

```
```class Node:

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

a = b = head

while b.next:

c = d = b.next

while d:

if b.data > d.data:

if b.next == d:

if b == head:

b.next = d.next
d.next = b
b, d = d, b
c = d
d = d.next

else:

b.next = d.next
d.next = b
a.next = d
b, d = d, b
c = d
d = d.next

else:

if b == head:

r = b.next
b.next = d.next
d.next = r
c.next = b
b, d = d, b
c = d
d = d.next

else:

r = b.next
b.next = d.next
d.next = r
c.next = b
a.next = d
b, d = d, b
c = d
d = d.next

else:

c = d
d = d.next

a = b
b = b.next

print(head.data, end = " ")

if __name__ == "__main__":

```

#### Output:

2->3->4->5

Time Complexity: O(N2), where N is the number of nodes present in the Linked List.

[forminator_quiz id="3483"]

### Key Takeaways

This blog tried to explain the selection sort algorithm over a linked list in an iterative fashion and also described its approach and time & space complexities. To practice more such problems on the linked list you can check out PrepBytes – Linked List