Introduction to Bubble Sort

Bubble Sort is the simplest sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they're in the wrong order. The algorithm gets its name because smaller elements "bubble" to the top of the list.

---

Bubble Sort Algorithm Visualization

Pass 1: [5, 1, 4, 2, 8]
Step 1: Compare 5 and 1 → swap → [1, 5, 4, 2, 8]
Step 2: Compare 5 and 4 → swap → [1, 4, 5, 2, 8]
Step 3: Compare 5 and 2 → swap → [1, 4, 2, 5, 8]
Step 4: Compare 5 and 8 → no swap → [1, 4, 2, 5, 8]
Pass 2: [1, 4, 2, 5, 8]
Step 1: Compare 1 and 4 → no swap → [1, 4, 2, 5, 8]
Step 2: Compare 4 and 2 → swap → [1, 2, 4, 5, 8]
Step 3: Compare 4 and 5 → no swap → [1, 2, 4, 5, 8]
Pass 3: [1, 2, 4, 5, 8]
Step 1: Compare 1 and 2 → no swap → [1, 2, 4, 5, 8]
Step 2: Compare 2 and 4 → no swap → [1, 2, 4, 5, 8]
Pass 4: [1, 2, 4, 5, 8] - Sorted!

---

Basic Bubble Sort Implementation

1. Simple Bubble Sort

#include <stdio.h>
// Function to perform bubble sort
void bubbleSort(int arr[], int n) {
int i, j, temp;
// Outer loop for number of passes
for (i = 0; i < n - 1; i++) {
// Inner loop for comparing adjacent elements
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Function to print array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
bubbleSort(arr, n);
printf("Sorted array:   ");
printArray(arr, n);
return 0;
}

Output:

Original array: 64 34 25 12 22 11 90 
Sorted array:   11 12 22 25 34 64 90

---

Optimized Bubble Sort

2. Bubble Sort with Early Termination

#include <stdio.h>
#include <stdbool.h>
// Optimized bubble sort with early termination
void optimizedBubbleSort(int arr[], int n) {
int i, j, temp;
bool swapped;
for (i = 0; i < n - 1; i++) {
swapped = false;
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no swapping occurred, array is already sorted
if (!swapped) {
printf("Array sorted after %d passes\n", i + 1);
break;
}
}
}
int main() {
int arr1[] = {64, 34, 25, 12, 22, 11, 90};
int arr2[] = {1, 2, 3, 4, 5, 6, 7};  // Already sorted
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
printf("Testing with unsorted array:\n");
printf("Original: ");
printArray(arr1, n1);
optimizedBubbleSort(arr1, n1);
printf("Sorted:   ");
printArray(arr1, n1);
printf("\nTesting with already sorted array:\n");
printf("Original: ");
printArray(arr2, n2);
optimizedBubbleSort(arr2, n2);
printf("Sorted:   ");
printArray(arr2, n2);
return 0;
}

Output:

Testing with unsorted array:
Original: 64 34 25 12 22 11 90 
Array sorted after 6 passes
Sorted:   11 12 22 25 34 64 90 
Testing with already sorted array:
Original: 1 2 3 4 5 6 7 
Array sorted after 1 passes
Sorted:   1 2 3 4 5 6 7

3. Bubble Sort with Step-by-Step Visualization

#include <stdio.h>
#include <stdbool.h>
void bubbleSortWithSteps(int arr[], int n) {
int i, j, temp;
bool swapped;
int pass = 1;
printf("Starting Bubble Sort...\n");
printf("Initial array: ");
printArray(arr, n);
printf("\n");
for (i = 0; i < n - 1; i++) {
swapped = false;
printf("Pass %d:\n", pass++);
for (j = 0; j < n - i - 1; j++) {
printf("  Comparing %d and %d: ", arr[j], arr[j + 1]);
if (arr[j] > arr[j + 1]) {
printf("SWAP ");
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
} else {
printf("no swap ");
}
printf("→ ");
printArray(arr, n);
}
if (!swapped) {
printf("  No swaps in this pass - array is sorted!\n");
break;
}
printf("\n");
}
}
int main() {
int arr[] = {5, 1, 4, 2, 8};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSortWithSteps(arr, n);
printf("\nFinal sorted array: ");
printArray(arr, n);
return 0;
}

Output:

Starting Bubble Sort...
Initial array: 5 1 4 2 8 
Pass 1:
Comparing 5 and 1: SWAP → 1 5 4 2 8 
Comparing 5 and 4: SWAP → 1 4 5 2 8 
Comparing 5 and 2: SWAP → 1 4 2 5 8 
Comparing 5 and 8: no swap → 1 4 2 5 8 
Pass 2:
Comparing 1 and 4: no swap → 1 4 2 5 8 
Comparing 4 and 2: SWAP → 1 2 4 5 8 
Comparing 4 and 5: no swap → 1 2 4 5 8 
Pass 3:
Comparing 1 and 2: no swap → 1 2 4 5 8 
Comparing 2 and 4: no swap → 1 2 4 5 8 
No swaps in this pass - array is sorted!
Final sorted array: 1 2 4 5 8

---

Bubble Sort Variations

4. Bubble Sort for Different Data Types

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
// Bubble sort for integers
void bubbleSortInt(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Bubble sort for floats
void bubbleSortFloat(float arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
float temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Bubble sort for characters
void bubbleSortChar(char arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
char temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Bubble sort for strings
void bubbleSortString(char arr[][100], int n) {
char temp[100];
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (strcmp(arr[j], arr[j + 1]) > 0) {
strcpy(temp, arr[j]);
strcpy(arr[j], arr[j + 1]);
strcpy(arr[j + 1], temp);
}
}
}
}
int main() {
// Integer array
int intArr[] = {64, 34, 25, 12, 22, 11, 90};
int intSize = sizeof(intArr) / sizeof(intArr[0]);
bubbleSortInt(intArr, intSize);
printf("Sorted integers: ");
for (int i = 0; i < intSize; i++) {
printf("%d ", intArr[i]);
}
printf("\n");
// Float array
float floatArr[] = {3.14, 2.71, 1.618, 0.577, 2.302};
int floatSize = sizeof(floatArr) / sizeof(floatArr[0]);
bubbleSortFloat(floatArr, floatSize);
printf("Sorted floats:   ");
for (int i = 0; i < floatSize; i++) {
printf("%.3f ", floatArr[i]);
}
printf("\n");
// Character array
char charArr[] = {'z', 'a', 'm', 'b', 'c', 'x'};
int charSize = sizeof(charArr) / sizeof(charArr[0]);
bubbleSortChar(charArr, charSize);
printf("Sorted chars:    ");
for (int i = 0; i < charSize; i++) {
printf("%c ", charArr[i]);
}
printf("\n");
// String array
char strArr[][100] = {"banana", "apple", "orange", "grape", "kiwi"};
int strSize = sizeof(strArr) / sizeof(strArr[0]);
bubbleSortString(strArr, strSize);
printf("Sorted strings:  ");
for (int i = 0; i < strSize; i++) {
printf("%s ", strArr[i]);
}
printf("\n");
return 0;
}

5. Bubble Sort with Comparison Function (Generic)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int (*CompareFunc)(const void*, const void*);
// Generic bubble sort using function pointer
void bubbleSortGeneric(void* arr, int n, size_t size, CompareFunc cmp) {
char* array = (char*)arr;
char* temp = (char*)malloc(size);
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
void* elem1 = array + j * size;
void* elem2 = array + (j + 1) * size;
if (cmp(elem1, elem2) > 0) {
// Swap elements
memcpy(temp, elem1, size);
memcpy(elem1, elem2, size);
memcpy(elem2, temp, size);
}
}
}
free(temp);
}
// Comparison functions
int compareInt(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int compareFloat(const void* a, const void* b) {
float diff = *(float*)a - *(float*)b;
return (diff > 0) - (diff < 0);
}
int compareString(const void* a, const void* b) {
return strcmp(*(const char**)a, *(const char**)b);
}
int compareIntDesc(const void* a, const void* b) {
return *(int*)b - *(int*)a;
}
int main() {
// Integer array
int intArr[] = {64, 34, 25, 12, 22, 11, 90};
int intSize = sizeof(intArr) / sizeof(intArr[0]);
bubbleSortGeneric(intArr, intSize, sizeof(int), compareInt);
printf("Sorted ints (asc):  ");
for (int i = 0; i < intSize; i++) printf("%d ", intArr[i]);
printf("\n");
bubbleSortGeneric(intArr, intSize, sizeof(int), compareIntDesc);
printf("Sorted ints (desc): ");
for (int i = 0; i < intSize; i++) printf("%d ", intArr[i]);
printf("\n");
// Float array
float floatArr[] = {3.14, 2.71, 1.618, 0.577, 2.302};
int floatSize = sizeof(floatArr) / sizeof(floatArr[0]);
bubbleSortGeneric(floatArr, floatSize, sizeof(float), compareFloat);
printf("Sorted floats:      ");
for (int i = 0; i < floatSize; i++) printf("%.3f ", floatArr[i]);
printf("\n");
// String array
const char* strArr[] = {"banana", "apple", "orange", "grape", "kiwi"};
int strSize = sizeof(strArr) / sizeof(strArr[0]);
bubbleSortGeneric(strArr, strSize, sizeof(char*), compareString);
printf("Sorted strings:     ");
for (int i = 0; i < strSize; i++) printf("%s ", strArr[i]);
printf("\n");
return 0;
}

---

Bubble Sort with Different Orderings

6. Ascending and Descending Order

#include <stdio.h>
#include <stdbool.h>
// Bubble sort in ascending order
void bubbleSortAscending(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Bubble sort in descending order
void bubbleSortDescending(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] < arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Bubble sort with flag for order
void bubbleSortWithOrder(int arr[], int n, bool ascending) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (ascending ? (arr[j] > arr[j + 1]) : (arr[j] < arr[j + 1])) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr1[] = {64, 34, 25, 12, 22, 11, 90};
int arr2[] = {64, 34, 25, 12, 22, 11, 90};
int arr3[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr1) / sizeof(arr1[0]);
printf("Original array: ");
printArray(arr1, n);
bubbleSortAscending(arr1, n);
printf("Ascending:      ");
printArray(arr1, n);
bubbleSortDescending(arr2, n);
printf("Descending:     ");
printArray(arr2, n);
bubbleSortWithOrder(arr3, n, true);
printf("With order(true): ");
printArray(arr3, n);
return 0;
}

---

Performance Analysis

7. Bubble Sort Performance Measurement

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
// Function to generate random array
void generateRandomArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
arr[i] = rand() % 1000;
}
}
// Function to copy array
void copyArray(int source[], int dest[], int n) {
for (int i = 0; i < n; i++) {
dest[i] = source[i];
}
}
// Standard bubble sort
void bubbleSortStandard(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Optimized bubble sort
void bubbleSortOptimized(int arr[], int n) {
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
// Measure execution time
double measureTime(void (*sortFunc)(int[], int), int arr[], int n, int iterations) {
clock_t start, end;
double total = 0;
for (int i = 0; i < iterations; i++) {
int* tempArr = (int*)malloc(n * sizeof(int));
copyArray(arr, tempArr, n);
start = clock();
sortFunc(tempArr, n);
end = clock();
total += ((double)(end - start)) / CLOCKS_PER_SEC;
free(tempArr);
}
return total / iterations;
}
int main() {
srand(time(NULL));
// Test with different array sizes
int sizes[] = {100, 500, 1000, 5000, 10000};
int numSizes = sizeof(sizes) / sizeof(sizes[0]);
int iterations = 5;
printf("=== Bubble Sort Performance Analysis ===\n");
printf("%-10s %-20s %-20s %-20s\n", "Size", "Standard (sec)", "Optimized (sec)", "Improvement");
printf("%-10s %-20s %-20s %-20s\n", "----", "---------------", "---------------", "-----------");
for (int i = 0; i < numSizes; i++) {
int n = sizes[i];
int* arr = (int*)malloc(n * sizeof(int));
generateRandomArray(arr, n);
double standardTime = measureTime(bubbleSortStandard, arr, n, iterations);
double optimizedTime = measureTime(bubbleSortOptimized, arr, n, iterations);
double improvement = ((standardTime - optimizedTime) / standardTime) * 100;
printf("%-10d %-20.6f %-20.6f %-20.2f%%\n", 
n, standardTime, optimizedTime, improvement);
free(arr);
}
// Test best case (already sorted)
printf("\n=== Best Case (Already Sorted) ===\n");
int bestCase[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int n = 10;
double standardBest = measureTime(bubbleSortStandard, bestCase, n, 1000);
double optimizedBest = measureTime(bubbleSortOptimized, bestCase, n, 1000);
printf("Standard:  %.6f sec\n", standardBest);
printf("Optimized: %.6f sec\n", optimizedBest);
printf("Improvement: %.2f%%\n", ((standardBest - optimizedBest) / standardBest) * 100);
// Test worst case (reverse sorted)
printf("\n=== Worst Case (Reverse Sorted) ===\n");
int worstCase[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
double standardWorst = measureTime(bubbleSortStandard, worstCase, n, 1000);
double optimizedWorst = measureTime(bubbleSortOptimized, worstCase, n, 1000);
printf("Standard:  %.6f sec\n", standardWorst);
printf("Optimized: %.6f sec\n", optimizedWorst);
printf("Improvement: %.2f%%\n", ((standardWorst - optimizedWorst) / standardWorst) * 100);
return 0;
}

---

Bubble Sort on Linked Lists

8. Bubble Sort for Linked List

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
// Function to create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to print linked list
void printList(Node* head) {
Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// Function to get length of linked list
int getLength(Node* head) {
int count = 0;
Node* current = head;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
// Bubble sort for linked list
void bubbleSortLinkedList(Node* head) {
if (head == NULL || head->next == NULL) {
return;
}
int swapped;
Node* current;
Node* last = NULL;
do {
swapped = 0;
current = head;
while (current->next != last) {
if (current->data > current->next->data) {
// Swap data
int temp = current->data;
current->data = current->next->data;
current->next->data = temp;
swapped = 1;
}
current = current->next;
}
last = current;
} while (swapped);
}
// Optimized bubble sort for linked list with early termination
void optimizedBubbleSortLinkedList(Node* head) {
if (head == NULL || head->next == NULL) {
return;
}
int length = getLength(head);
int swapped;
for (int i = 0; i < length - 1; i++) {
swapped = 0;
Node* current = head;
for (int j = 0; j < length - i - 1; j++) {
if (current->data > current->next->data) {
int temp = current->data;
current->data = current->next->data;
current->next->data = temp;
swapped = 1;
}
current = current->next;
}
if (!swapped) break;
}
}
int main() {
// Create a linked list: 64 -> 34 -> 25 -> 12 -> 22 -> 11 -> 90
Node* head = createNode(64);
head->next = createNode(34);
head->next->next = createNode(25);
head->next->next->next = createNode(12);
head->next->next->next->next = createNode(22);
head->next->next->next->next->next = createNode(11);
head->next->next->next->next->next->next = createNode(90);
printf("Original linked list: ");
printList(head);
bubbleSortLinkedList(head);
printf("Sorted linked list:   ");
printList(head);
// Free memory
Node* current = head;
while (current != NULL) {
Node* temp = current;
current = current->next;
free(temp);
}
return 0;
}

---

Bubble Sort with Recursion

9. Recursive Bubble Sort

#include <stdio.h>
// Recursive bubble sort
void recursiveBubbleSort(int arr[], int n) {
// Base case
if (n == 1) {
return;
}
// One pass of bubble sort
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
// Recursive call for remaining elements
recursiveBubbleSort(arr, n - 1);
}
// Optimized recursive bubble sort
void recursiveBubbleSortOptimized(int arr[], int n, int* swapped) {
// Base case
if (n == 1) {
return;
}
int localSwapped = 0;
// One pass of bubble sort
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
localSwapped = 1;
if (swapped != NULL) *swapped = 1;
}
}
// Recursive call only if swaps occurred
if (localSwapped) {
recursiveBubbleSortOptimized(arr, n - 1, swapped);
}
}
int main() {
int arr1[] = {64, 34, 25, 12, 22, 11, 90};
int arr2[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr1) / sizeof(arr1[0]);
printf("Original array: ");
printArray(arr1, n);
recursiveBubbleSort(arr1, n);
printf("Recursive sort: ");
printArray(arr1, n);
int swapped = 0;
recursiveBubbleSortOptimized(arr2, n, &swapped);
printf("Optimized recursive: ");
printArray(arr2, n);
printf("Swaps occurred: %s\n", swapped ? "Yes" : "No");
return 0;
}

---

Bubble Sort Analysis

Time Complexity

Case	Time Complexity	Description
Best Case	O(n)	Array already sorted (with optimization)
Average Case	O(n²)	Random order
Worst Case	O(n²)	Array reverse sorted

Space Complexity

Type	Space Complexity	Description
In-place	O(1)	Only requires a single additional memory space
Recursive	O(n)	Call stack for recursive version

Comparison with Other Sorts

Algorithm	Best Case	Average Case	Worst Case	Space
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)

---

Advantages and Disadvantages

Advantages

1. Simple implementation - Easy to understand and code
2. Stable sort - Maintains relative order of equal elements
3. In-place sorting - Requires O(1) extra space
4. Adaptive - Can detect already sorted arrays (optimized version)
5. Educational value - Excellent for teaching sorting concepts

Disadvantages

1. Inefficient - O(n²) time complexity makes it impractical for large datasets
2. Many swaps - Performs many swap operations
3. Not suitable - For real-world applications with large data
4. Poor performance - On reverse-sorted data

---

When to Use Bubble Sort

Suitable Scenarios

• Small datasets (n < 100)
• Educational purposes - Teaching sorting algorithms
• Nearly sorted data - With optimization, can be efficient
• Memory-constrained environments - In-place sorting
• When simplicity is priority over performance

When NOT to Use

• Large datasets - Performance degrades quickly
• Real-time applications - Too slow
• Production systems - Better algorithms exist
• Performance-critical code - Use O(n log n) sorts

---

Conclusion

Bubble Sort is the simplest sorting algorithm, making it excellent for learning but impractical for large-scale applications:

Key Takeaways

1. Basic algorithm - Repeatedly compares and swaps adjacent elements
2. Optimization - Early termination when no swaps occur
3. Time complexity - O(n²) average/worst case, O(n) best case
4. Space complexity - O(1) in-place sorting
5. Stability - Maintains order of equal elements
6. Adaptability - Can handle various data types

Optimizations Summary

• Early termination - Stop when no swaps occur
• Cocktail shaker - Bidirectional passes (not covered)
• Comb sort - Uses gap > 1 (advanced variation)

Educational Value

Despite its inefficiency, Bubble Sort remains valuable for:

• Understanding sorting concepts
• Learning algorithm analysis
• Recognizing optimization opportunities
• Building foundation for more complex algorithms

For production code, use more efficient algorithms like Quick Sort or Merge Sort, but for learning and small datasets, Bubble Sort provides a clear, understandable introduction to sorting.