Bubble Sort is one of the simplest sorting algorithms, which repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Despite its simplicity, it is inefficient for large datasets because of its O(n²) time complexity. Bubble Sort is often used for educational purposes to understand sorting concepts and algorithm behavior.
Understanding the Problem
The main idea behind Bubble Sort is to “bubble up” the largest (or smallest) elements to their correct positions through repeated swapping. Each pass moves the next largest element to its final position. Optimization can be applied to stop the algorithm early if the array becomes sorted before completing all passes.
Program 1: Iterative Bubble Sort
This program demonstrates Bubble Sort using nested loops to sort an integer array in ascending order.
#include <stdio.h>
// Function to perform bubble sort
void bubbleSort(int arr[], int size) {
int temp;
for (int i = 0; i < size - 1; i++) {
int swapped = 0; // Optimization: Track swaps
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap adjacent elements
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
// If no elements were swapped in inner loop, array is sorted
if (!swapped) break;
}
}
// Function to display array
void display(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {4, 7, 8, 1, 5, 3, 2, 6, 9};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
display(arr, size);
bubbleSort(arr, size);
printf("Sorted array: ");
display(arr, size);
return 0;
}The algorithm uses nested loops to repeatedly compare and swap elements. The optimization with a swapped flag helps avoid unnecessary passes if the array becomes sorted early.
Program 2: Recursive Bubble Sort
This program demonstrates Bubble Sort using recursion, which reduces the problem size in each call by one.
#include <stdio.h>
// Recursive bubble sort function
void bubbleSortRecursive(int arr[], int size) {
if (size <= 1) return; // Base case
for (int i = 0; i < size - 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
bubbleSortRecursive(arr, size - 1);
}
// Function to display array
void display(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {4, 7, 8, 1, 5, 3, 2, 6, 9};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
display(arr, size);
bubbleSortRecursive(arr, size);
printf("Sorted array: ");
display(arr, size);
return 0;
}The recursive approach sorts the largest element in each call and then recursively sorts the remaining array. It demonstrates how a simple iterative algorithm can be expressed recursively.
FAQs
Q1: What is the time complexity of Bubble Sort?
Worst and average case: O(n²), best case with optimization: O(n).
Q2: Is Bubble Sort stable?
Yes, Bubble Sort maintains the relative order of equal elements.
Q3: Is Bubble Sort suitable for large arrays?
No, it is inefficient for large datasets; algorithms like Quick Sort or Merge Sort are better.
Q4: Can Bubble Sort be implemented in descending order?
Yes, simply change the comparison to swap if arr[i] < arr[i + 1].
Q5: Can bubble sort handle arrays with duplicate elements?
Yes, bubble sort can sort arrays with duplicate elements without any issue. Duplicate values will simply remain in their relative positions after sorting.
Conclusion
Bubble Sort is a simple and easy-to-understand sorting algorithm, useful for learning sorting logic and algorithm behavior. While not practical for large datasets, it provides a foundation for understanding more advanced sorting algorithms. Both iterative and recursive implementations demonstrate flexibility in programming approaches.
References & Additional Resources
- Kernighan, Brian W., and Dennis M. Ritchie. The C Programming Language. 2nd Edition, Prentice Hall, 1988.
- Data Structures Using C by Reema Thareja – A comprehensive textbook (2nd Edition, 2011) that introduces C basics and covers data structures like arrays, linked lists, trees, graphs, and more — with examples, exercises, and analysis.
- Programiz – Bubble Sort Tutorial – Well-structured guide covering how Bubble Sort compares, swaps, and sorts—for novices and those brushing up on basics.
- Wikipedia: Bubble sort – In-depth overview including time/space complexities, history, and variations, written clearly and backed by sources.
