selection Sort Linked List Algorithm
The Selection Sort Linked List Algorithm is an efficient sorting technique that operates on a linked list data structure. This algorithm sorts the elements in a linked list by iteratively selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion. The main idea behind this algorithm is to divide the list into two parts: the sorted part, which starts as an empty list, and the unsorted part. The algorithm repeatedly selects the minimum (or maximum) element from the unsorted part and moves it to the end of the sorted part. This process continues until the unsorted part becomes empty and the sorted part contains all the elements in the desired order.
In the context of a linked list, the selection sort algorithm involves updating the pointers of the nodes to rearrange the elements, rather than swapping the elements themselves. The algorithm starts by initializing a pointer to the current minimum (or maximum) element and traverses the list, comparing each element with the current minimum. If a smaller (or larger) element is found, the pointer is updated to point to the new minimum (or maximum) element. Once the end of the list is reached, the minimum (or maximum) element is moved to the sorted portion by updating the appropriate pointers. This process is repeated until the entire list is sorted. While the selection sort algorithm has a time complexity of O(n^2) for both average and worst-case scenarios, which is not optimal compared to other sorting algorithms, it still proves to be a simple and intuitive method for sorting linked lists.
#include <iostream>
using namespace std;
//node defined
class node
{
public:
int data;
node *link;
node(int d)
{
data = d;
link = NULL;
}
};
//printing the linked list
void print(node *head)
{
node *current = head;
while (current != NULL)
{
cout << current->data << " ";
current = current->link;
}
cout << endl;
}
//creating the linked list with 'n' nodes
node *createlist(int n)
{
node *head = NULL;
node *t = NULL;
for (int i = 0; i < n; i++)
{
node *temp = NULL;
int num;
cin >> num;
temp = new node(num);
if (head == NULL)
{
head = temp;
t = temp;
continue;
}
if (t->link == NULL)
t->link = temp;
t = temp;
}
return head;
}
//performing selection sort on the linked list in an iterative manner
void my_selection_sort_linked_list(node *&head)
{
node *min = head; //throughout the algorithm 'min' is used to denote the node with min value out of all the nodes left for scanning
//while scanning if we find a node 'X' with value lesser than min,
//then we update the pointers in such a way that 'X' becomes the predecessor of 'min'
node *current = min->link; // 'current' refers to the current node we are scanning
node *previous = min; //'previous' refers to the node that is previous to the current node
node *temp = NULL; // 'temp' in this algo is used to point to the last node of the sorted part of the linked list.
//eg. If at any time instance the state of the linked list is suppose 1->2->5->3->8->NULL
//then, we see that "1->2" is the sorted part of the LL, and therefore temp will be pointing to the last node of the sorted part,i.e,'2'
//We keep on arranging the Linked list in such a way that after each iteration the node with 'min' value is placed at its correct position.
//Eg. Let suppose initially we have 5->4->1->3->2->NULL
//After 1st iteration : 1->4->5->3->2->NULL and so on
while (min->link != NULL) //so that all the nodes are scanned or until there exists a node
{
//pick the first node from the unsorted part and assume that it is the minimum and then start scanning from the next node
while (current != NULL) //suppose you choose the min node to be X, then scan starts from the (X+1)th node until its NULL. current = (X+1)th node and min = X
{
if (current->data < min->data) //if the current node is smaller than the presumed node 'min'
{
if (temp == NULL) //temp stays null for the first iteration, therefore it symbolizes that we are scanning for the first time
{
if (previous == min) //if the 'previous' is pointing to the 'min' node
{
//Update the pointers
head = current; //update the head pointer with the current node
min->link = current->link;
current->link = previous;
min = current;
current = previous->link;
}
else //if the 'previous' is not pointing to the 'min' node
{
//Update the pointers
head = current; //update the head pointer with the current node
previous->link = current->link;
current->link = min;
min = current;
current = previous->link;
}
}
else //if 'temp' is not NULL, i.e., its not the 1st iteration
{
temp->link = current;
previous->link = current->link;
current->link = min;
min = current;
current = previous->link;
}
}
else //if the current node is greater than min, just move the previous and the current pointer a step further
{
previous = previous->link;
current = current->link;
}
}
//update the pointers. Set 'temp' to the last node in the sorted part. Make 'min' move a step further so that 'min' points to the 1st node of the unsorted part
//start the iteration again
temp = min;
min = min->link;
previous = min;
current = min->link;
}
}
// Test cases:
// enter the no. of nodes : 5
// 8 9 3 1 4
// original list is : 8 9 3 1 4
// sorted list is : 1 3 4 8 9
// enter the no. of nodes : 3
// -1 -2 -3
// original list is : -1 -2 -3
// sorted list is : -3 -2 -1
// enter the no. of nodes : 8
// 8 7 6 5 4 3 2 1
// original list is : 8 7 6 5 4 3 2 1
// sorted list is : 1 2 3 4 5 6 7 8
// enter the no. of nodes : 6
// 5 3 4 1 -2 -4
// original list is : 5 3 4 1 -2 -4
// sorted list is : -4 -2 1 3 4 5
int main()
{
node *head = NULL;
int n;
cout << "enter the no. of nodes : "; //taking input from user about the number of nodes in linked list
cin >> n;
if (n == 0)
return 0;
head = createlist(n); //creating the list
cout << "original list is : ";
print(head); //printing the original linked list
my_selection_sort_linked_list(head); //applying selection sort
cout << "sorted list is : ";
print(head); //printing the sorted linked list
return 0;
}
