Data Structure

A Linked list data structure is efficient enough comparing to an Array. In this article, we will discuss how to implement the selection sort algorithm using Linked List.

[This article is applicable especially for a singly linked list, but it is also applicable in a doubly linked list. I prefer C++ for this article. But you are free to use C or another programming languages for which, you feel comfortable.]

  • If you have visited this page accidentally and don’t know what is linked list or how to implement it, you are invited to the following article:

What is Linked list? How to implement a linked list with C++?

  • Step – 1: First of all, we need to implement a normal singly linked list. After implementation, we have the following code:
#include <iostream>
using namespace std;
struct Node
{
int data; //the data part of the Node.
Node *next; //Pointer that have the link (reference) to the next node.
};

Node *head = NULL;

int getData()
{
int data;
cout << "Input an integer as data: ";
cin >> data;
return data;
}

void addData(Node *targetNode, int data)
{
targetNode -> data = data;
}

void createNewNode(Node *prevNode)
{
Node *newNode = new Node;
addData(newNode, getData()); //storing data to the new node.
newNode -> next = NULL;
prevNode -> next = newNode;
}

void createList(int total)
{
Node *Current = head = new Node;
addData(Current, getData());
for(int i = 1; i < total; i++)
{
createNewNode(Current);
Current = Current -> next;
}
}

void showList()
{
Node *Current = head;
cout << "Showing the linked list:" << endl;
if(Current == NULL)
{
cout << "Empty list!" << endl;
return;
}
while(Current != NULL)
{
cout << Current -> data << " ";
Current = Current -> next; //Now, Current pointer is pointing it next Node.
}
cout << endl;
}

void selectionSort()
{
Node *selectedNode = head;
while(selectedNode -> next != NULL)
{
Node *currentNode = selectedNode;
Node *minimumNode = currentNode;
int minimumData = currentNode -> data;
while(currentNode != NULL)
{
if(minimumData > currentNode -> data)
{
minimumData = currentNode -> data;
minimumNode = currentNode;
}

currentNode = currentNode -> next;
}
int tempSwap = minimumNode -> data;
minimumNode -> data = selectedNode -> data;
selectedNode -> data = tempSwap;
selectedNode = selectedNode -> next;
}
}

int main()
{
createList(5);
showList();
selectionSort();

showList();
return 0;
}
  • Step – 2: Let’s discuss the Selection Sort algorithm for a Linked List:
Selection sort algorithm for a linked list is almost
the same as the selection sort algorithm for an array.

 

  1. We have to take a pointer to Node(struct) that will point at head.
  2. Using a loop, we will traverse the linked list till we don’t get the next Node is NULL.
  3. We will take a normal variable to store the minimum value of data.
  4. Then we will traverse the linked list (using a nested loop) each time from the selected node to the last node to get the minimum value between the currently selected node to the last node.
  5. After that will store the reference of the minimum node to a pointer which will keep track of the current minimum node. At the same time, we will store the minimum value of data in a normal variable.
  6. Now, we will swap the data values between the currently selected node and the minimum node.

And, this is our simple algorithm to sort a linked list.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.