DAA: Bubble Sort Algorithm on Linked List
Bubble Sort Algorithm on Linked List
In this article, we will sort a Link List using the bubble sort technique.
Example:
Input : 20->30->40->10
Output :10->20->30->40
Input : 20->4->3
Output : 3->4->20
Sorting Technique
The bubble sort technique works similarly as it takes two adjacent elements, compares them and the swaps the smaller one with larger one. At the end of pass 1, the largest element reaches its final position.
C Code:
#include <stdio.h>
#include <malloc.h>
/* Link list node */
typedef struct node {
int data;
struct node* next;
} node;
node* head = NULL;
/*Function to create a linked list*/
void createll()
{
int i, n;
node* tail; // keeps track of the last element
tail = head; //atm head is the last element
int arr[4] = { 20, 30, 40, 10};
for (i = 0; i < 4; i++) {
node* newn;
newn = (node*)malloc(sizeof(node)); //creates a new node in every iteration
newn->data = arr[i];
newn->next = NULL;
if (head == NULL) {
head = newn;
tail = head;
}
else {
tail->next = newn; //linking the previous last element to new last element
tail = newn; //making the new element as the last element
}
}
}
/* Function to print linked list */
void display()
{
struct node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
/* function to swap data of two nodes a and b*/
void swap(node* a, node* b)
{
int temp = a->data;
a->data = b->data;
b->data = temp;
}
/*Function to bubble sort*/
void bubble()
{
int ctr, n = 1;
node *t1, *t2;
t1 = head;
do {
ctr = 0;
t2 = head;
while (t2->next != NULL) {
if (t2->data > t2->next->data) {
swap(t2, t2->next);
ctr = 1;
}
t2 = t2->next;
}
t1 = t1->next;
n++;
} while (t1->next != NULL && ctr);
}
void main()
{
createll();
printf("Before Sorting: ");
display();
bubble();
printf("\nAfter Sorting: ");
display();
}
C++ Code:
#include <iostream>
using namespace std;
struct node {
int data;
node* next;
}* head = NULL;
bool Is_List_Empty()
{
if (head == NULL)
return true;
return false;
}
void Insert_At_End(int value)
{
node *temp = new node, *current = head;
temp->data = value;
temp->next = NULL;
if (Is_List_Empty()) {
head = temp;
return;
}
while (current->next != NULL)
current = current->next;
current->next = temp;
}
void Bubble_Sort()
{
int cnt = 0;
node* start = head;
node* curr = NULL;
node* trail = NULL;
node* tmp = NULL;
//get cnt(size) of linked list
while (start != NULL) {
start = start->next;
++cnt;
}
for (int i = 0; i < cnt; ++i) {
//set curr and trail at the start node
curr = trail = head;
while (curr->next != NULL) {
//compares curr and its next
if (curr->data > curr->next->data) {
//swaps pointers for curr & curr->next
tmp = curr->next;
curr->next = curr->next->next;
tmp->next = curr;
//setup pointers for the head and trail if applicable
if (curr == head)
head = trail = tmp;
else
trail->next = tmp;
curr = tmp;
}
//advance pointers
trail = curr;
curr = curr->next;
}
}
}
void Print_Linked_List()
{
if (Is_List_Empty()) {
cout << "List is Empty" << endl;
return;
}
node* current = head;
while (current->next != NULL) {
cout << current->data << " ";
current = current->next;
}
cout << current->data << endl;
}
int main()
{
int i;
cout << "Before sorting: ";
int arr[4] = { 20, 30, 40, 10 };
for (i = 0; i < 4; i++)
Insert_At_End(arr[i]);
Print_Linked_List();
Bubble_Sort();
cout << "After sorting: ";
Print_Linked_List();
return 0;
}
Java Code:
public
class Linked_List_Bubble_Sort {
public
static void main(String[] args)
{
LinkedList list = new LinkedList();
// Adding integers unordered
list.insertAtTop(10);
list.insertAtTop(40);
list.insertAtTop(30);
list.insertAtTop(20);
// Prints the integers before sorting
System.out.print("Before sorting: ");
list.print();
// Call BubbleSort method
list.bubbleSort();
// Prints out the integers after sorting
System.out.print("After sorting: ");
list.print();
}
static class Node {
private
int item;
private
Node next;
// Constructor
public
Node(int newItem, Node newNode)
{
item = newItem;
next = newNode;
}
// Getter's and Setters
public
int getItem()
{
return item;
}
public
void setItem(int newItem)
{
item = newItem;
}
public
Node getNext()
{
return next;
}
public
void setNext(Node newNext)
{
next = newNext;
}
}
static class LinkedList {
private
Node top;
public
LinkedList()
{
top = null;
}
public
void insertAtTop(int value)
{
Node newNode = new Node(value, top);
top = newNode;
}
public
void print()
{
Node curr = top;
while (curr != null) {
System.out.print(curr.getItem() + " ");
curr = curr.getNext();
}
System.out.println();
}
public
void bubbleSort()
{
Node curr = top;
Node prev = null;
int temp = 0;
while (curr.getNext() != null) {
prev = top;
while (prev.getNext() != null) {
// If previous item is greater than current
if (prev.getItem() > prev.getNext().getItem()) {
temp = prev.getItem();
// Make the swap
prev.setItem(prev.getNext().getItem());
prev.getNext().setItem(temp);
}
prev = prev.getNext();
}
curr = curr.getNext();
}
}
}
}
Output:
Before sorting: 20 30 40 10 After sorting: 10 20 30 40
Time complexity: O(n*n)
