NBC 103 • Unit 516 min read★ High Exam Frequency
Sorting Algorithms: Bubble Sort, Selection Sort & Insertion Sort
Unit 5: Searching, Sorting, Dynamic Memory & File Handling • Problem Solving Using C
👨🏫 Professor's Mental Model: Soda Carbonation Bubbles vs Playing Cards in Bridge
Bubble Sort cold drink ke soda bubbles jaisa hai: sabse bada element har pass me bubble ki tarah upar uth kar aakhri me settle ho jata hai! Selection Sort class ke sabse chote bache ko dhoondh kar line ke aage khada karne jaisa hai (Minimum Swap)! Aur Insertion Sort taash ke patte (playing cards) jamane jaisa hai: naya card uthao aur use purane sorted patton ke beech sahi jagah par insert kar do!
Academic Lecture Notes & Solved Study Pages
Unit 5 • Core Concepts, Step-by-Step Proofs & Notebook Solutions
NOTEBOOK PAGE 1 OF 3• Lecture Study Sheet
1. Bubble Sort: Adjacent Comparison & Optimization
Mechanism: Compares adjacent elements `arr[j]` and `arr[j+1]`. If out of order, they are swapped. At the end of Pass $k$, the $k$-th largest element is guaranteed to have bubbled to its final position.
Total Passes required: $N - 1$.
Total Comparisons: $\frac{N(N-1)}{2} = O(N^2)$.
Optimization: Introduce a `swapped` boolean flag. If an entire pass completes without a single swap, the array is already sorted, terminating early in $O(N)$ best-case time!
NOTEBOOK PAGE 2 OF 3• Lecture Study Sheet
2. Selection Sort: Minimum Element Placement
Mechanism:
1. Divide array conceptually into Sorted and Unsorted subarrays.
2. Scan unsorted subarray to find the index of the minimum element (`min_idx`).
3. Swap `arr[min_idx]` with `arr[i]` (the first unsorted slot).
Key Advantage: Performs at most $N - 1$ swaps in total, making it optimal when writing to flash memory where write cycles are costly. Time Complexity: $O(N^2)$ across all cases.
NOTEBOOK PAGE 3 OF 3• Lecture Study Sheet
3. Insertion Sort: Card-Deck In-Place Sorting
Mechanism: Iterates through array, picking element `key` and shifting all elements greater than `key` one position to the right to open an insertion slot.
Key Advantage: Highly adaptive for nearly-sorted data (Best Case $O(N)$), online algorithm (sorts data as it arrives in a stream), and Stable (preserves original order of duplicates).
Master Comparative Matrix: Bubble vs Selection vs Insertion Sort
| Algorithm | Best Case Time | Avg Case Time | Worst Case Time | Space Complexity | Stable? | Swaps (Worst Case) |
|---|---|---|---|---|---|---|
| Bubble Sort (Optimized) | O(N) | O(N^2) | O(N^2) | O(1) | Yes | O(N^2) |
| Selection Sort | O(N^2) | O(N^2) | O(N^2) | O(1) | No | O(N) (At most N-1) |
| Insertion Sort | O(N) | O(N^2) | O(N^2) | O(1) | Yes | O(N^2) |
Interactive Tested Code Example
#include <stdio.h>
#include <stdbool.h>
// Optimized Bubble Sort with Early Termination Flag
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap adjacent elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no two elements were swapped in this pass, array is sorted!
if (!swapped) break;
}
}
int main(void) {
int data[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(data) / sizeof(data[0]);
printf("Unsorted Array: ");
for (int i = 0; i < n; i++) printf("%d ", data[i]);
printf("\n");
bubble_sort(data, n);
printf("Sorted Array: ");
for (int i = 0; i < n; i++) printf("%d ", data[i]);
printf("\n");
return 0;
}💡 Note:Implements optimized Bubble Sort featuring the swapped boolean flag to terminate early in O(N) time if the array becomes sorted before N-1 passes.
🎯 University Exam Scoring Blueprint
- In university exams, always trace pass-by-pass iterations for an unsorted sample array (e.g. 5, 1, 4, 2, 8).
- Contrast the minimum swaps of Selection Sort (O(N)) with Bubble Sort (O(N^2)).
- Define Algorithm Stability: an algorithm is stable if it preserves the relative order of duplicate elements.
Top Viva Questions on Sorting Algorithms: Bubble Sort, Selection Sort & Insertion Sort
1
What is an In-Place Sorting Algorithm?
2