Bubble sort
Bubble sort is a sorting algoritm that compares two adjacent elements and swaps them until they are in the intended order. Just like the movement of air bubbles in the water that rise up to the surface, each element of the array moves to the end in each iteration. Therefore, it is called a bubble sort.
Working of Bubble Sort Suppose we are trying to sort the elements in ascending order.
- First Iteration (Compare and Swap)
- Starting from the first index, compare the first and the second elements.
- If the first element is greater than the second element, they are swapped.
- Now, compare the second and the third elements. Swap them if they are not in order.
- The above process goes on until the last element
Pass 1:
Compare 5 and 3 → swap → [3, 5, 8, 4, 1, 12, 7]
Compare 5 and 8 → no swap → [3, 5, 8, 4, 1, 12, 7]
Compare 8 and 4 → swap → [3, 5, 4, 8, 1, 12, 7]
Compare 8 and 1 → swap → [3, 5, 4, 1, 8, 12, 7]
Compare 8 and 12 → no swap → [3, 5, 4, 1, 8, 12, 7]
Compare 12 and 7 → swap → [3, 5, 4, 1, 8, 7, 12]
Pass 2:
Compare 3 and 5 → no swap
Compare 5 and 4 → swap → [3, 4, 5, 1, 8, 7, 12]
Compare 5 and 1 → swap → [3, 4, 1, 5, 8, 7, 12]
Compare 5 and 8 → no swap
Compare 8 and 7 → swap → [3, 4, 1, 5, 7, 8, 12]
Pass 3:
Compare 3 and 4 → no swap
Compare 4 and 1 → swap → [3, 1, 4, 5, 7, 8, 12]
Compare 4 and 5 → no swap
Compare 5 and 7 → no swap
Pass 4:
Compare 3 and 1 → swap → [1, 3, 4, 5, 7, 8, 12]
Compare 3 and 4 → no swap
Compare 4 and 5 → no swap
Pass 5:
Compare 1 and 3 → no swap
Compare 3 and 4 → no swap
Final Sorted Array:[1, 3, 4, 5, 7, 8, 12]
Bubble sort code:
# Bubble Sort
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
def print_array(arr):
for num in arr:
print(num, end=" ")
print()
arr = [64, 34, 25, 12, 22, 11, 90]
print("Before Sorting:")
print_array(arr)
bubble_sort(arr)
print("After Sorting:")
print_array(arr)
public class BubbleSort {
// Bubble Sort function
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped)
break;
}
}
// Print array
public static void printArray(int[] arr) {
for (int num : arr)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Before Sorting:");
printArray(arr);
bubbleSort(arr);
System.out.println("After Sorting:");
printArray(arr);
}
}
#include <stdio.h>
void bubbleSort(int arr[], int n) {
int swapped;
for (int i = 0; i < n - 1; i++) {
swapped = 0;
for (int j = 0; j arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (!swapped)
break;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {64,34,25,12,22,11,90};
int n = 7;
printf("Before Sorting:\n");
printArray(arr, n);
bubbleSort(arr, n);
printf("After Sorting:\n");
printArray(arr, n);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
void bubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped)
break;
}
}
void printArray(vector<int> arr) {
for (int num : arr)
cout << num << " ";
cout << endl;
}
int main() {
vector<int> arr = {64,34,25,12,22,11,90};
cout << "Before Sorting:" << endl;
printArray(arr);
bubbleSort(arr);
cout << "After Sorting:" << endl;
printArray(arr);
return 0;
}
| Case | Time Complexity | Explanation |
| Best Case | O(n) | When the array is already sorted. Only one pass is needed. |
| Average Case | O(n²) | When elements are in random order. Multiple passes are required. |
| Worst Case | O(n²) | When the array is in reverse order (completely unsorted). |
Space Complexity:
- O (1) (in-place sorting, no extra space used)
Note: Bubble Sort is simple but inefficient for large datasets due to its quadratic time complexity in most cases. It is mainly used for educational purposes.