Linked List: Perform bubble sort on singly linked list

To perform bubble sort, we follow below steps:

Step 1: Check if data on the 2 adjacent nodes are in ascending order or not. If not, swap the data of the 2 adjacent nodes.

Step 2: At the end of pass 1, the largest element will be at the end of the list. In 2nd pass 2nd largest element will be at its position.

Step 3: We terminate the loop, when all the elements are started.

Solution in C++

#include<iostream>
#include<vector>
#include<string>

using namespace std;

struct Node
{
	int data;
	Node *next;

	Node(int x)
	{
		data = x;
		next = NULL;
	}
};

void print_list(Node *head)
{
	Node *start = head;

	while(start)
	{
		cout<<start->data<<" -> ";
		start = start->next;
	}
	cout<<"\n\n";
}

void my_swap (Node *node_1, Node *node_2)
{
	int temp = node_1->data;
	node_1->data = node_2 -> data;
	node_2 -> data = temp;
}

void bubble_sort(Node *head)
{
	int swapped;

	Node *lPtr; // left pointer will always point to the start of the list
	Node *rPrt = NULL; // right pointer will always point to the end of the list
	do
	{	
		swapped = 0;
		lPtr = head;
		while(lPtr->next != rPrt)
		{
			if (lPtr->data > lPtr->next->data) 
			{
				my_swap(lPtr, lPtr->next); 
                swapped = 1; 
			}
			lPtr = lPtr->next;
		}
		//as the largest element is at the end of the list, assign that to rPtr as there is no need to
		//check already sorted list
		rPrt = lPtr;

	}while(swapped);
}

int main()
{
	Node *head = new Node(2);
	head -> next = new Node(1);
	head -> next -> next = new Node(4);
	head -> next -> next -> next = new Node(3);
	head -> next -> next -> next  -> next = new Node(6);
	head -> next -> next -> next  -> next -> next = new Node(5);

	cout<<"The original list = "<<endl;
	print_list(head);


	bubble_sort(head);

	cout<<"The Sorted list = "<<endl;
	print_list(head);

	return 0;
}

Output:

The original list =
2 -> 1 -> 4 -> 3 -> 6 -> 5 ->

The Sorted list =
1 -> 2 -> 3 -> 4 -> 5 -> 6 ->