Bubble Sort
In this page:
Basic Idea
Bubble sort repeatedly steps through the array, comparing each pair of adjacent elements and swapping them if they're in the wrong order, so that with each full pass the largest remaining unsorted value 'bubbles up' to its correct position at the end.
Example: Basic Idea
#include <iostream>
using namespace std;
int main() {
int arr[] = {5, 1, 4, 2, 8};
int n = 5;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {5, 1, 4, 2, 8};
int n = arr.length;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) { int t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t; }
System.out.println(Arrays.toString(arr));
}
}arr = [5, 1, 4, 2, 8]
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
print(arr)#include <stdio.h>
int main() {
int arr[] = {5, 1, 4, 2, 8};
int n = 5;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) { int t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t; }
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}Login to try C/C++/Java code in the editor
Step by Step
Each pass compares neighboring elements from left to right; if a swap happens anywhere in a pass, the array wasn't fully sorted yet, so another pass is needed. This repeats until a full pass completes with zero swaps, confirming the array is sorted.
Example: Step by Step
#include <iostream>
using namespace std;
int main() {
int arr[] = {5, 1, 4, 2, 8};
int n = 5;
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]) { swap(arr[j], arr[j + 1]); swapped = true; }
if (!swapped) break;
}
for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {5, 1, 4, 2, 8};
int n = arr.length;
boolean 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 t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t; swapped = true; }
if (!swapped) break;
}
System.out.println(Arrays.toString(arr));
}
}arr = [5, 1, 4, 2, 8]
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(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
print(arr)#include <stdio.h>
#include <stdbool.h>
int main() {
int arr[] = {5, 1, 4, 2, 8};
int n = 5;
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 t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t; swapped = true; }
if (!swapped) break;
}
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}Login to try C/C++/Java code in the editor
Small Array
Tracing bubble sort on a small array like [5, 1, 4, 2] by hand — watching each adjacent comparison and swap — makes the bubbling behavior concrete and shows exactly why the largest values settle into place first.
Example: Small Array
#include <iostream>
using namespace std;
int main() {
int arr[] = {5, 1, 4, 2};
int n = 4;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
cout << "Comparing " << arr[j] << " and " << arr[j + 1] << endl;
if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
}
}
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {5, 1, 4, 2};
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
System.out.println("Comparing " + arr[j] + " and " + arr[j + 1]);
if (arr[j] > arr[j + 1]) { int t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t; }
}
}
}
}arr = [5, 1, 4, 2]
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
print("Comparing", arr[j], "and", arr[j + 1])
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]#include <stdio.h>
int main() {
int arr[] = {5, 1, 4, 2};
int n = 4;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
printf("Comparing %d and %d\n", arr[j], arr[j + 1]);
if (arr[j] > arr[j + 1]) { int t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t; }
}
}
return 0;
}Login to try C/C++/Java code in the editor
Practice
Try modifying the input array and adding a swap counter or print statement inside the loop to watch how many comparisons and swaps different starting arrangements require, especially comparing an already-sorted array against a reverse-sorted one.
Example: Practice
#include <iostream>
using namespace std;
int main() {
int arr[] = {9, 3, 7, 1};
int n = 4, swaps = 0;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); swaps++; }
cout << "Total swaps: " << swaps;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {9, 3, 7, 1};
int n = arr.length, swaps = 0;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) { int t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t; swaps++; }
System.out.println("Total swaps: " + swaps);
}
}arr = [9, 3, 7, 1]
n = len(arr)
swaps = 0
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swaps += 1
print("Total swaps:", swaps)#include <stdio.h>
int main() {
int arr[] = {9, 3, 7, 1};
int n = 4, swaps = 0;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) { int t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t; swaps++; }
printf("Total swaps: %d", swaps);
return 0;
}Login to try C/C++/Java code in the editor
Summary
Bubble sort runs in O(n²) time in the worst and average case, which makes it too slow for large datasets in practice, but its simplicity makes it a useful first example before moving on to faster algorithms like merge sort or quicksort.
Example: Summary
#include <iostream>
using namespace std;
int main() {
cout << "Bubble sort: O(n^2) worst/average time, simple but slow for large datasets";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Bubble sort: O(n^2) worst/average time, simple but slow for large datasets");
}
}print("Bubble sort: O(n^2) worst/average time, simple but slow for large datasets")#include <stdio.h>
int main() {
printf("Bubble sort: O(n^2) worst/average time, simple but slow for large datasets");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 9 topics to unlock
0/9 topics done
Complete these topics first: