Bubble Sort is one of the simplest sorting algorithms. It works by repeatedly swapping adjacent elements if they are in the wrong order. This process is repeated until the array is sorted.
Key Concepts of Bubble Sort
- Comparison and Swapping:
- Each pair of adjacent elements is compared.
- If the first element is greater than the second, they are swapped.
- Passes:
- Each pass moves the largest unsorted element to its correct position.
- With each pass, the unsorted portion of the array becomes smaller.
- Optimization:
- The algorithm can be optimized to stop early if no swaps are made during a pass, indicating that the array is already sorted.
Characteristics of Bubble Sort
- Time Complexity:
- Best Case: O(n)O(n)O(n) (if the array is already sorted).
- Worst Case: O(n2)O(n^2)O(n2) (for a completely unsorted array).
- Average Case: O(n2)O(n^2)O(n2).
- Space Complexity:
- O(1)O(1)O(1) (in-place sorting).
- Stability:
- Bubble Sort is stable because it does not change the relative order of equal elements.
Implementation of Bubble Sort in C
C Code Example:
#include <stdio.h>
// Function to perform Bubble Sort
void bubbleSort(int arr[], int n) {
int swapped;
for (int i = 0; i < n – 1; i++) {
swapped = 0; // Reset swap flag
// Perform a single pass
for (int j = 0; j < n – i – 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1; // Set swap flag
}
}
// If no swaps were made, the array is already sorted
if (swapped == 0) {
break;
}
}
}
// Utility function to print an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf(“%d “, arr[i]);
}
printf(“\n”);
}
// Main function
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;
}
How It Works
Example Walkthrough:
For the array {64, 34, 25, 12, 22, 11, 90}:
- First Pass:
- Compare 64 and 34 → Swap → {34, 64, 25, 12, 22, 11, 90}
- Compare 64 and 25 → Swap → {34, 25, 64, 12, 22, 11, 90}
- Compare 64 and 12 → Swap → {34, 25, 12, 64, 22, 11, 90}
- Compare 64 and 22 → Swap → {34, 25, 12, 22, 64, 11, 90}
- Compare 64 and 11 → Swap → {34, 25, 12, 22, 11, 64, 90}
- Compare 64 and 90 → No Swap → {34, 25, 12, 22, 11, 64, 90}.
The largest element (90) is now in the correct position.
- Second Pass:
- Similar process moves the next largest element (64) to its correct position.
- Subsequent Passes:
- Continue until the array is sorted.
Final Sorted Array:
{11, 12, 22, 25, 34, 64, 90}
Optimized Bubble Sort
To avoid unnecessary comparisons, we use a swapped flag. If no elements are swapped during a pass, the algorithm terminates early, as the array is already sorted.
Advantages and Disadvantages
Advantages:
- Simple to understand and implement.
- Suitable for small datasets.
- In-place sorting (no extra memory needed).
Disadvantages:
- Inefficient for large datasets.
- High number of comparisons, especially for larger arrays.
Example Output
For the input array {64, 34, 25, 12, 22, 11, 90}:
Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90
Bubble Sort is primarily used for educational purposes and small datasets due to its simplicity. For large datasets, more efficient algorithms like Quick Sort or Merge Sort are preferred.