🟦 Bubble Sort: A Classic Sorting Algorithm
A clear, practical write-up for learners and interview preparation — pseudo code, examples, MCQs, assignments (C / Java / Python), and further reading.
🔹 Introduction
Sorting is one of the most fundamental problems in computer science. It appears frequently in interviews, coding tests, and day-to-day software tasks. Bubble Sort, while not the most efficient for large datasets, is an excellent pedagogical tool: it helps beginners understand comparisons, swaps, loops, and basic complexity analysis.
- Builds a strong foundation in algorithm analysis.
- Common in teaching Data Structures & Algorithms (DSA).
- Useful for interview questions that test understanding of loops, in-place operations, and optimization flags.
🔹 What is Bubble Sort?
Bubble Sort is a comparison-based algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. The largest elements gradually "bubble" to the end of the list after every pass.
✨ Pseudo Code
procedure bubbleSort(A)
n = length(A)
repeat
swapped = false
for i = 1 to n-1
if A[i] > A[i+1] then
swap(A[i], A[i+1])
swapped = true
end for
until not swapped
end procedure
🔹 Illustration (sample run)
Input: [5, 3, 8, 4, 2]
- After Pass 1: [3, 5, 4, 2, 8]
- After Pass 2: [3, 4, 2, 5, 8]
- After Pass 3: [3, 2, 4, 5, 8]
- After Pass 4: [2, 3, 4, 5, 8] — Sorted
🔹 Different Implementations
1) Standard Bubble Sort
for i = 0 to n-1
for j = 0 to n-i-1
if A[j] > A[j+1]
swap(A[j], A[j+1])
Time Complexity: Best O(n)*, Average O(n²), Worst O(n²).
Space Complexity: O(1) (in-place)
*Best-case O(n) when you use the 'swapped' optimization and the array is already sorted.
2) Optimized Bubble Sort (early stop)
for i = 0 to n-1
swapped = false
for j = 0 to n-i-1
if A[j] > A[j+1]
swap(A[j], A[j+1])
swapped = true
if not swapped
break
The optimization stops early if no swaps happen during a full pass (array already sorted), reducing passes and giving a best-case of O(n).
3) Recursive Bubble Sort (conceptual)
procedure recursiveBubble(A, n)
if n == 1 then return
for i = 0 to n-2
if A[i] > A[i+1] then swap(A[i], A[i+1])
recursiveBubble(A, n-1)
Equivalent O(n²) time complexity; offered for academic completeness, but iterative versions are preferred in practice.
🔹 Spin-offs & Useful Tricks
Because Bubble Sort naturally places the largest element at the end after the first pass, it becomes convenient for related tasks:
- Find largest: After one pass, the last element is the largest.
- Find 2nd largest: After two passes, the second-last element is the second largest.
- Find nth largest/smallest: Run Bubble Sort for n passes and read the required position.
These tricks are useful for small datasets or as educational exercises, but for production use on large data prefer selection/heap algorithms or partial selection algorithms (like Quickselect).
🔹 History of Bubble Sort
Bubble Sort is one of the earliest sorting algorithms taught in computer science. Its simple compare-and-swap approach made it an ideal first example in textbooks and classrooms. Though not widely used in high-performance systems, its role in teaching fundamentals of sorting and algorithmic complexity is timeless.
🔹 10 MCQs (options shown — click to reveal answer)
1. Bubble Sort is an example of?
- A) Divide and Conquer
- B) Comparison-based Sorting
- C) Hashing
- D) Dynamic Programming
Show Answer
2. Worst-case time complexity of Bubble Sort?
- A) O(n)
- B) O(log n)
- C) O(n²)
- D) O(n log n)
Show Answer
3. Best-case complexity of Bubble Sort?
- A) O(n)
- B) O(n²)
- C) O(log n)
- D) O(n log n)
Show Answer
4. Is Bubble Sort stable?
- A) No
- B) Yes
- C) Depends on implementation
- D) None of the above
Show Answer
5. Bubble Sort is an ____ algorithm?
- A) In-place
- B) Out-of-place
- C) Recursive only
- D) None of the above
Show Answer
6. Bubble Sort is suitable for?
- A) Large datasets
- B) Small datasets
- C) Any size dataset
- D) Streaming data
Show Answer
7. Bubble Sort is also known as?
- A) Quick Sort
- B) Sinking Sort
- C) Selection Sort
- D) Merge Sort
Show Answer
8. Which method shares adjacent swap logic?
- A) Insertion Sort
- B) Merge Sort
- C) Quick Sort
- D) Heap Sort
Show Answer
9. Can Bubble Sort detect already sorted arrays early?
- A) No
- B) Yes, with optimization
- C) Sometimes
- D) None of the above
Show Answer
10. Space complexity of Bubble Sort?
- A) O(n)
- B) O(log n)
- C) O(1)
- D) O(n log n)
Show Answer
🔹 10 Assignments (solutions hidden — click to view)
Assignment 1 — Implement Bubble Sort in C
Show Solution (C)
#include <stdio.h>
void bubbleSort(int arr[], int n) {
for (int i=0; i<n-1; i++) {
for (int j=0; j<n-i-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
int main() {
int arr[] = {5, 3, 8, 4, 2};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
for (int i=0; i<n; i++) printf("%d ", arr[i]);
return 0;
}
Assignment 2 — Implement Bubble Sort in Java
Show Solution (Java)
public class BubbleSort {
public static void bubbleSort(int[] arr) {
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 tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {5,3,8,4,2};
bubbleSort(arr);
for (int v : arr) System.out.print(v + " ");
}
}
Assignment 3 — Implement Bubble Sort in Python
Show Solution (Python)
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
if __name__ == "__main__":
arr = [5,3,8,4,2]
bubble_sort(arr)
print(arr)
Assignment 4 — Modify Bubble Sort to sort in descending order
Show Hint / Solution
Change the comparison from > to <. For example, in Python: if arr[j] < arr[j+1]: swap(...)
Assignment 5 — Find the second largest element using Bubble Sort idea
Show Hint / Solution
Run Bubble Sort for two passes; after the second pass the second-last element is the 2nd largest. Or maintain the largest and second-largest while scanning in O(n).
Assignment 6 — Count the number of swaps performed
Show Solution
# Python example
def bubble_swap_count(arr):
n = len(arr)
swaps = 0
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return swaps
Assignment 7 — Detect a sorted array early (use swapped flag)
Show Solution
Use a boolean swapped flag inside the outer loop. If after a full inner loop no swaps occurred, break early.
Assignment 8 — Implement Bubble Sort on a linked list
Show Hint
Swap node data or adjust node links while iterating until no swaps remain. Complexity is O(n²) still.
Assignment 9 — Implement recursive Bubble Sort
Show Hint
Bubble the largest to end, then call recursion on n-1 elements. Base case n==1.
Assignment 10 — Compare Bubble Sort with Selection Sort
Show Notes
Both have O(n²) time. Selection Sort typically performs fewer swaps (O(n) swaps) while Bubble Sort may do many swaps. Selection Sort is not stable by default; Bubble Sort is stable.
0 Comments