Bubble Sort: flowchart, algorithm and program
This program reads n numbers into an array a[] and sorts them in ascending order using bubble sort. It repeatedly compares neighbouring elements a[j] and a[j + 1] and swaps them if they are in the wrong order, so the largest values slowly "bubble" to the end.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Read n.
- Step 3: Set i = 0.
- Step 4: If i < n, go to step 5; otherwise go to step 7.
- Step 5: Read a[i].
- Step 6: Set i = i + 1. Go to step 4.
- Step 7: Set i = 0.
- Step 8: If i < n - 1, go to step 9; otherwise go to step 15.
- Step 9: Set j = 0.
- Step 10: If j < n - i - 1, go to step 11; otherwise go to step 14.
- Step 11: If a[j] > a[j+1], go to step 12; otherwise go to step 13.
- Step 12: Swap a[j] and a[j+1] using temp.
- Step 13: Set j = j + 1. Go to step 10.
- Step 14: Set i = i + 1. Go to step 8.
- Step 15: Print "Sorted array:".
- Step 16: Set i = 0.
- Step 17: If i < n, go to step 18; otherwise go to step 20.
- Step 18: Print a[i].
- Step 19: Set i = i + 1. Go to step 17.
- Step 20: Stop.
Pseudocode
BEGIN
READ n
i ← 0
WHILE i < n DO
READ a[i]
i ← i + 1
END WHILE
i ← 0
WHILE i < n - 1 DO
j ← 0
WHILE j < n - i - 1 DO
IF a[j] > a[j+1] THEN
Swap a[j] and a[j+1] using temp
END IF
j ← j + 1
END WHILE
i ← i + 1
END WHILE
PRINT "Sorted array:"
i ← 0
WHILE i < n DO
PRINT a[i]
i ← i + 1
END WHILE
END
Program in C, Python and Java
Bubble Sort program in C
#include <stdio.h>
int main() {
int n, i, j, temp;
int a[100];
printf("Enter n: ");
scanf("%d", &n);
printf("Enter %d numbers: ", n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
printf("Sorted array: ");
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}Bubble Sort program in Python
n = int(input("Enter n: "))
a = list(map(int, input("Enter " + str(n) + " numbers: ").split()))
for i in range(n - 1):
for j in range(n - i - 1):
if a[j] > a[j + 1]:
temp = a[j]
a[j] = a[j + 1]
a[j + 1] = temp
print("Sorted array:", *a)Bubble Sort program in Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n, i, j, temp;
System.out.print("Enter n: ");
n = sc.nextInt();
int[] a = new int[n];
System.out.print("Enter " + n + " numbers: ");
for (i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
System.out.print("Sorted array: ");
for (i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}
Sample input: n = 5, numbers = 64 25 12 22 11
Output: Sorted array: 11 12 22 25 64
How it works
- The first loop reads n numbers into a[0] to a[n-1].
- The outer loop with i runs n - 1 times. Each pass places the next largest value at its final position at the end of the array.
- The inner loop with j compares a[j] and a[j + 1]. If a[j] > a[j + 1], the two are swapped using the helper variable temp.
- The inner loop stops at n - i - 1 because the last i elements are already sorted after i passes, so there is no need to check them again.
- For 64 25 12 22 11: pass 1 gives 25 12 22 11 64, pass 2 gives 12 22 11 25 64, pass 3 gives 12 11 22 25 64, pass 4 gives 11 12 22 25 64. The final loop prints the sorted array.
Dry run (trace table)
| Step | Line | Box | n | i | a | j | temp | Output |
|---|---|---|---|---|---|---|---|---|
| 1 | 3 | Start | ||||||
| 2 | 8 | Read n | 5 | |||||
| 3 | 11 | i = 0 | 5 | 0 | ||||
| 4 | 11 | i < n? | 5 | 0 | ||||
| 5 | 12 | Read a[i] | 5 | 0 | [64] | |||
| 6 | 11 | i = i + 1 | 5 | 1 | [64] | |||
| 7 | 11 | i < n? | 5 | 1 | [64] | |||
| 8 | 12 | Read a[i] | 5 | 1 | [64,25] | |||
| 9 | 11 | i = i + 1 | 5 | 2 | [64,25] | |||
| 10 | 11 | i < n? | 5 | 2 | [64,25] | |||
| 11 | 12 | Read a[i] | 5 | 2 | [64,25,12] | |||
| 12 | 11 | i = i + 1 | 5 | 3 | [64,25,12] | |||
| 13 | 11 | i < n? | 5 | 3 | [64,25,12] | |||
| 14 | 12 | Read a[i] | 5 | 3 | [64,25,12,22] | |||
| 15 | 11 | i = i + 1 | 5 | 4 | [64,25,12,22] | |||
| 16 | 11 | i < n? | 5 | 4 | [64,25,12,22] | |||
| 17 | 12 | Read a[i] | 5 | 4 | [64,25,12,22,11] | |||
| 18 | 11 | i = i + 1 | 5 | 5 | [64,25,12,22,11] | |||
| 19 | 11 | i < n? | 5 | 5 | [64,25,12,22,11] | |||
| 20 | 15 | i = 0 | 5 | 0 | [64,25,12,22,11] |
Time and space complexity
Time: O(n²) · Space: O(1). The nested loops compare adjacent pairs about n²/2 times, and sorting is done in place with only a temp variable.
Common mistakes
- Running the inner loop up to n - 1 instead of n - i - 1. This either compares already sorted items needlessly or, if written as j < n, reads a[j + 1] outside the array.
- Swapping without a temp variable, for example writing a[j] = a[j + 1]; a[j + 1] = a[j];. This makes both elements equal and loses a value.
- Using >= instead of > in the comparison. It still sorts, but it swaps equal elements for no reason.
Viva questions
Q1. What is the purpose of the variable temp in lines 18-20?
It holds a[j] temporarily so the two elements can be swapped. Without it, assigning a[j] = a[j+1] would overwrite the original a[j] and we would lose that value.
Q2. Why does the inner loop run up to j < n - i - 1 and not always up to n - 1?
After each pass of the outer loop, the largest remaining element has bubbled to the end, so the last i elements are already in their final place. The inner loop skips them, and n - i - 1 also keeps a[j + 1] inside the array.
Q3. Why does the outer loop run only n - 1 times?
After n - 1 passes, n - 1 elements are in their correct positions, so the last remaining element must also be correct. A final nth pass would do no useful work.
Q4. What does the condition a[j] > a[j + 1] check, and what would change if you used < instead?
It checks whether two adjacent elements are in the wrong order for ascending sorting, and swaps them if so. With <, the array would be sorted in descending order.
Q5. What happens if the user enters n = 1, n = 0, or a negative n?
For n = 1 the outer loop runs 0 times (0 < 0 is false), so the single element is printed as it is. For n = 0 or negative n, no sorting loops run and nothing is read or printed. A value of n above 100 would overflow the array a[100], and the program does not check for that.
Q6. What is the time complexity of this bubble sort, and how many comparisons does it make?
It is O(n^2) in the best, average and worst cases, because there is no early-exit check. It makes (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparisons. Space complexity is O(1) since it sorts in place.
Q7. How would you improve this program so that it stops early on an already sorted array?
Add a flag such as swapped = 0 at the start of each outer pass and set it to 1 whenever a swap happens. If a full pass finishes with no swap, break out of the loop. The best case then becomes O(n).
Q8. Is bubble sort stable, and why?
Yes, it is stable. It swaps only when a[j] > a[j+1], strictly greater, so equal elements are never swapped and keep their original relative order.
Frequently asked questions
What is the time complexity of bubble sort?
The worst and average case is O(n^2) because of the two nested loops. Space used is O(1) since it sorts in place with only one temp variable.
Why does the outer loop run only n - 1 times?
After n - 1 passes, n - 1 elements are in their correct places, so the last remaining element must also be in place. An nth pass would do nothing.
How can I make bubble sort faster on sorted input?
Add a flag that is set when a swap happens. If a full pass makes no swap, the array is already sorted and you can break out early, giving O(n) for sorted input.