These are the notes for C Coding Questions, episode 13, placement practice for people who finished the SyntaxPilot C course. Sorting questions, part one: bubble sort with an early exit, selection sort with the fewest swaps, insertion sort on nearly sorted data, and what stable and unstable sorting mean, shown with real student records.
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was compiled with gcc -Wall -O2 -Wno-unused-result main.c -o main -lm (gcc 13.3, Linux x86-64, 32-bit int), the SyntaxPilot compiler's C command with warnings on, and every output below is real. The compiler stops a program after 8 seconds (Time Limit Exceeded), like an online judge.
Real-life pictures
| In real life | In C |
|---|---|
| the school assembly lines up by height: neighbours swap until nobody moves | bubble sort: compare and swap neighbours, pass after pass |
| a shopkeeper moves heavy boxes: find the lightest, one lift per place | selection sort: find the minimum, swap once |
| picking up playing cards: slide each new card left into place | insertion sort: shift bigger values right, drop the key in |
| two students with 75 marks: who is listed first? | stable vs unstable sorting |
Sorting means putting values in order. Ascending order is smallest first (1 2 4 5 8); descending is biggest first.
Q1: Bubble sort, with passes and swaps
Problem. Read n, then n integers. Sort them in ascending order with bubble sort and print how many passes and swaps it made. A pass is one walk from left to right that compares every pair of adjacent (neighbouring) values and swaps them (makes them trade places) if the left one is bigger.
| Input | Sorted |
|---|---|
5 1 4 2 8 |
1 2 4 5 8 |
5 4 3 2 1 |
1 2 3 4 5 |
1 2 3 4 5 |
1 2 3 4 5 |
3 1 3 1 |
1 1 3 3 |
Edge cases: already sorted, reversed, n = 1, n = 0, repeated values, a huge n.
Dry run: 5 1 4 2 8
A dry run means running the code by hand, step by step.
| Pass | Comparisons and swaps | After the pass | Swaps |
|---|---|---|---|
| 1 | 5>1 swap, 5>4 swap, 5>2 swap, 5<8 | 1 4 2 5 8 |
3 |
| 2 | 1<4, 4>2 swap, 4<5 | 1 2 4 5 8 |
1 |
| 3 | 1<2, 2<4 | 1 2 4 5 8 |
0 |
| 4 | 1<2 | 1 2 4 5 8 |
0 (wasted) |
After pass 1 the biggest value has "bubbled" to the end, which is where the name comes from. Each pass can stop one place earlier (j < n - 1 - pass), because the end is already sorted.
The obvious attempt: the textbook bubble sort
#include <stdio.h>
int a[100];
int main() {
int n, passes = 0, swaps = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int pass = 0; pass < n - 1; pass++) {
passes++;
for (int j = 0; j < n - 1 - pass; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
swaps++;
}
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\npasses %d, swaps %d\n", passes, swaps);
return 0;
}
| Input | Output |
|---|---|
5 / 5 1 4 2 8 |
1 2 4 5 8 · passes 4, swaps 4 |
5 / 5 4 3 2 1 |
1 2 3 4 5 · passes 4, swaps 10 |
5 / 1 2 3 4 5 |
1 2 3 4 5 · passes 4, swaps 0 |
Correct, but it made four passes on input that was already sorted. Now the stress test: 300,000 values that are already in order (the program fills a[i] = i itself, input 300000):
#include <stdio.h>
int a[300000];
int main() {
int n, passes = 0, swaps = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) a[i] = i;
for (int pass = 0; pass < n - 1; pass++) {
passes++;
for (int j = 0; j < n - 1 - pass; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
swaps++;
}
}
printf("sorted %d values, passes %d, swaps %d\n", n, passes, swaps);
return 0;
}
Output:
Time Limit Exceeded
Why it is slow
The plain version always makes n - 1 passes, whatever the data: about n² / 2 comparisons. For n = 300,000 that is about 45 billion comparisons, even though not one swap is needed.
The fix: stop when a pass swaps nothing
If a whole pass makes no swap, every pair of neighbours is in order, so the array is sorted. Keep a flag (a variable that remembers whether something happened): swapped = 0 at the start of each pass, swapped = 1 on a swap, and if (!swapped) break; after the pass. This is the early exit.
#include <stdio.h>
int a[100];
int main() {
int n, passes = 0, swaps = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int pass = 0; pass < n - 1; pass++) {
int swapped = 0;
passes++;
for (int j = 0; j < n - 1 - pass; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
swaps++;
swapped = 1;
}
if (!swapped) break;
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\npasses %d, swaps %d\n", passes, swaps);
return 0;
}
| Input | Output |
|---|---|
5 / 5 1 4 2 8 |
1 2 4 5 8 · passes 3, swaps 4 |
5 / 1 2 3 4 5 |
1 2 3 4 5 · passes 1, swaps 0 |
5 / 5 4 3 2 1 |
1 2 3 4 5 · passes 4, swaps 10 |
1 / 7 |
7 · passes 0, swaps 0 |
0 |
(empty line) · passes 0, swaps 0 |
4 / 3 1 3 1 |
1 1 3 3 · passes 3, swaps 3 |
For n = 1 (and n = 0), pass < n - 1 is false at once, so there are zero passes. Equal values are never swapped, because the test is a[j] > a[j + 1] (strictly bigger).
And the stress test, with the early exit:
#include <stdio.h>
int a[300000];
int main() {
int n, passes = 0, swaps = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) a[i] = i;
for (int pass = 0; pass < n - 1; pass++) {
int swapped = 0;
passes++;
for (int j = 0; j < n - 1 - pass; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
swaps++;
swapped = 1;
}
if (!swapped) break;
}
printf("sorted %d values, passes %d, swaps %d\n", n, passes, swaps);
return 0;
}
Output:
sorted 300000 values, passes 1, swaps 0
Instant.
Complexity. Big O describes how the work grows as n grows. Best case (already sorted): one pass, O(n). Worst case (reversed): O(n²), about n² / 2 comparisons and swaps. Space: O(1), because it sorts in place, inside the same array, with only a few extra variables.
Q2: Sort with the fewest swaps (selection sort)
Problem. Every swap is a heavy lift. Sort n integers in ascending order using as few swaps as possible, and print the number of swaps.
| Input | Sorted | Fewest swaps |
|---|---|---|
5 4 3 2 1 |
1 2 3 4 5 |
2 |
1 2 3 4 5 |
1 2 3 4 5 |
0 |
4 4 2 2 1 1 |
1 1 2 2 4 4 |
2 |
Edge cases: sorted (0 swaps), reversed, repeated values.
The obvious attempt: swap whenever you see a smaller value
Many students write this and call it selection sort. For each place i, look at every later j, and swap at once whenever a[j] < a[i].
#include <stdio.h>
int a[100];
int main() {
int n, swaps = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (a[j] < a[i]) {
int t = a[i]; a[i] = a[j]; a[j] = t;
swaps++;
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\nswaps %d\n", swaps);
return 0;
}
| Input | Output |
|---|---|
5 / 5 4 3 2 1 |
1 2 3 4 5 · swaps 10 |
6 / 4 4 2 2 1 1 |
1 1 2 2 4 4 · swaps 6 |
Sorted, but ten heavy lifts for five boxes.
Why
It swaps every time it meets a smaller value, even when a still smaller one comes later. That is up to n² / 2 swaps.
The fix: remember the minimum index, swap once
While scanning, only remember where the smallest value is: the minimum index m. Looking is cheap; lifting is not. After the scan, swap a[i] with a[m] once, and only if m != i. One swap per place, so at most n − 1 swaps. This is real selection sort.
Dry run on 5 4 3 2 1:
| Place i | Smallest of the rest | Swap | Array after |
|---|---|---|---|
| 0 | 1 (index 4) | 5 ↔ 1 | 1 4 3 2 5 |
| 1 | 2 (index 3) | 4 ↔ 2 | 1 2 3 4 5 |
| 2 | 3 (index 2) | none, m == i | 1 2 3 4 5 |
| 3 | 4 (index 3) | none, m == i | 1 2 3 4 5 |
#include <stdio.h>
int a[100];
int main() {
int n, swaps = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n - 1; i++) {
int m = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[m]) m = j;
if (m != i) {
int t = a[i]; a[i] = a[m]; a[m] = t;
swaps++;
}
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\nswaps %d\n", swaps);
return 0;
}
| Input | Output |
|---|---|
5 / 5 4 3 2 1 |
1 2 3 4 5 · swaps 2 |
5 / 1 2 3 4 5 |
1 2 3 4 5 · swaps 0 |
6 / 4 4 2 2 1 1 |
1 1 2 2 4 4 · swaps 2 |
5 / 5 1 4 2 8 |
1 2 4 5 8 · swaps 2 |
1 / 7 |
7 · swaps 0 |
Complexity. Always about n² / 2 comparisons, O(n²) even on sorted input, because it scans the whole rest for every place. At most n − 1 swaps. Space O(1).
Stable or unstable? Two students with 75
A record is a group of values that belong together, here a name and marks, stored in a struct. The key is the value we sort by: marks. A sort is stable if records with equal keys keep their input order; otherwise it is unstable.
Input: Asha 75, Neha 75, Ravi 60, Priya 90. A stable sort by marks must print Asha before Neha.
#include <stdio.h>
struct student { char name[20]; int marks; };
struct student s[100];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%19s %d", s[i].name, &s[i].marks);
for (int i = 0; i < n - 1; i++) {
int m = i;
for (int j = i + 1; j < n; j++)
if (s[j].marks < s[m].marks) m = j;
struct student t = s[i]; s[i] = s[m]; s[m] = t;
}
for (int i = 0; i < n; i++) printf("%s %d\n", s[i].name, s[i].marks);
return 0;
}
Input 4 / Asha 75 / Neha 75 / Ravi 60 / Priya 90:
Ravi 60
Neha 75
Asha 75
Priya 90
Neha before Asha: selection sort is not stable. The first swap (place 0 with Ravi at index 2) threw Asha over Neha to the third place. A long-distance swap can jump over an equal record.
Q3: Sort a nearly sorted list (insertion sort)
Problem. A merit list of 300,000 values is already sorted. One late entry, the smallest of all, is added at the end. Sort the list again, and keep equal marks in their input order.
| Input | Output |
|---|---|
0 1 2 … 299998, -1 |
-1 0 1 2 … 299998 |
Edge cases: nearly sorted, reversed, equal marks, n = 1.
The obvious attempt: reuse selection sort
#include <stdio.h>
int a[300000];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) a[i] = i;
a[n - 1] = -1;
long long moves = 0;
for (int i = 0; i < n - 1; i++) {
int m = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[m]) m = j;
if (m != i) {
int t = a[i]; a[i] = a[m]; a[m] = t;
moves++;
}
}
printf("first %d, last %d, moves %lld\n", a[0], a[n - 1], moves);
return 0;
}
Input 300000:
Time Limit Exceeded
And selection sort isn't stable anyway.
Why
Selection sort scans the whole rest of the array for every place, sorted or not: about n² / 2 = 45 billion comparisons.
The fix: insertion sort
Like playing cards: take the next value, the key (key = a[i]). Everything before it is already sorted. While the value on its left is bigger than key, shift it one place right (a[j + 1] = a[j], a copy, cheaper than a swap). Then drop key into the gap (a[j + 1] = key). A value already in place costs one comparison and nothing moves, so nearly sorted data (only a few values out of place) takes close to O(n).
Dry run on 5 1 4 2 8:
| i | key | Shifted | Array after | Shifts |
|---|---|---|---|---|
| 1 | 1 | 5 | 1 5 4 2 8 |
1 |
| 2 | 4 | 5 | 1 4 5 2 8 |
1 |
| 3 | 2 | 5, 4 | 1 2 4 5 8 |
2 |
| 4 | 8 | none | 1 2 4 5 8 |
0 |
Four shifts in total, the same as bubble sort's four swaps: both equal the number of inversions (pairs that are out of order).
#include <stdio.h>
int a[100];
int main() {
int n, shifts = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
shifts++;
}
a[j + 1] = key;
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\nshifts %d\n", shifts);
return 0;
}
| Input | Output |
|---|---|
5 / 5 1 4 2 8 |
1 2 4 5 8 · shifts 4 |
5 / 5 4 3 2 1 |
1 2 3 4 5 · shifts 10 |
5 / 1 2 3 4 5 |
1 2 3 4 5 · shifts 0 |
4 / 3 1 3 1 |
1 1 3 3 · shifts 3 |
1 / 7 |
7 · shifts 0 |
The order of the conditions matters: j >= 0 && a[j] > key. && stops at the first false part, so when j reaches -1, a[-1] is never read.
The nearly sorted merit list:
#include <stdio.h>
int a[300000];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) a[i] = i;
a[n - 1] = -1;
long long moves = 0;
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
moves++;
}
a[j + 1] = key;
}
printf("first %d, last %d, moves %lld\n", a[0], a[n - 1], moves);
return 0;
}
Input 300000:
first -1, last 299998, moves 299999
Instant. The late entry moved past 299,999 values, one shift each; every other value stayed put.
And stability, on the same four students:
#include <stdio.h>
struct student { char name[20]; int marks; };
struct student s[100];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%19s %d", s[i].name, &s[i].marks);
for (int i = 1; i < n; i++) {
struct student key = s[i];
int j = i - 1;
while (j >= 0 && s[j].marks > key.marks) {
s[j + 1] = s[j];
j--;
}
s[j + 1] = key;
}
for (int i = 0; i < n; i++) printf("%s %d\n", s[i].name, s[i].marks);
return 0;
}
Ravi 60
Asha 75
Neha 75
Priya 90
Asha stays before Neha: insertion sort is stable, because it shifts only while the left mark is strictly bigger, so an equal mark is never jumped over.
Complexity. Best case (sorted): O(n). Worst case (reversed): O(n²). Nearly sorted: close to O(n). Space O(1).
Complexity summary
| Sort | Best case | Worst case | Swaps / moves | Stable | Extra space |
|---|---|---|---|---|---|
| bubble sort (plain) | O(n²) | O(n²) | up to n²/2 swaps | yes | O(1) |
| bubble sort + early exit | O(n), sorted input | O(n²) | up to n²/2 swaps | yes | O(1) |
| "swap on every smaller" | O(n²) | O(n²) | up to n²/2 swaps | no | O(1) |
| selection sort | O(n²) | O(n²) | ≤ n − 1 swaps | no | O(1) |
| insertion sort | O(n), sorted input | O(n²) | shifts = inversions | yes | O(1) |
The best case is the input that makes an algorithm do the least work; the worst case, the most.
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
bubble sort with no swapped flag |
Time Limit Exceeded on 300,000 sorted values |
always n − 1 passes | if (!swapped) break; |
if (a[j] < a[i]) swap inside the scan |
no error: swaps 10 instead of swaps 2 |
lifts at every smaller value | remember m, swap once |
while (a[j] > key && j >= 0) |
undefined behaviour: reads a[-1] |
j is checked too late |
j >= 0 && a[j] > key |
if (a[j] >= a[j + 1]) swap |
no error: equal records change order | breaks stability | use > (strictly bigger) |
int swapped = 0; outside the pass loop |
the flag never goes back to 0: no early exit | it must be reset every pass | declare it inside the pass loop |
| selection sort for nearly sorted data | Time Limit Exceeded |
always n²/2 comparisons | insertion sort |
a[-1] is undefined behaviour (UB): the C standard makes no promise about what happens. The program may seem to work today, print garbage, or crash tomorrow, so no particular output can be relied on. Always test j >= 0 first.
Here is the >= mistake for real, a bubble sort on records that swaps equal marks:
#include <stdio.h>
struct student { char name[20]; int marks; };
int main() {
struct student s[] = {{"Asha", 75}, {"Neha", 75}, {"Ravi", 60}};
int n = 3;
for (int pass = 0; pass < n - 1; pass++)
for (int j = 0; j < n - 1 - pass; j++)
if (s[j].marks >= s[j + 1].marks) { /* >= : equal marks swap too */
struct student t = s[j]; s[j] = s[j + 1]; s[j + 1] = t;
}
for (int i = 0; i < n; i++) printf("%s %d\n", s[i].name, s[i].marks);
return 0;
}
Output:
Ravi 60
Neha 75
Asha 75
With > it prints Ravi 60, Asha 75, Neha 75, stable again.
Your turn: count the inversions (solution)
Problem. An inversion is a pair of positions i < j with a[i] > a[j], a pair that is out of order. Count the inversions without sorting. 5 1 4 2 8 → 4, 5 4 3 2 1 → 10, 1 2 3 → 0.
Idea. The inversion count equals the number of swaps bubble sort makes (and the shifts insertion sort makes): every adjacent swap fixes exactly one inversion. Count it directly with a double loop over all pairs, O(n²). Use long long: n = 100,000 can have about 5 billion inversions. With merge sort it can be done in O(n log n): try it once you know merge sort.
Show the solution
#include <stdio.h>
int main() {
int n, a[1000];
scanf("%d", &n);
if (n < 0 || n > 1000) {
printf("n must be 0 to 1000\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
long long inv = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (a[i] > a[j]) inv++;
printf("inversions %lld\n", inv);
return 0;
}
| Input | Output |
|---|---|
5 / 5 1 4 2 8 |
inversions 4 |
5 / 5 4 3 2 1 |
inversions 10 |
3 / 1 2 3 |
inversions 0 |
0 |
inversions 0 |
Practice questions (with solutions)
1. Sort in descending order. Change one comparison of insertion sort.
Solution
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] < key) { /* < instead of > : biggest first */
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Input 6 / 3 9 1 9 4 7:
9 9 7 4 3 1
2. A stable selection sort. Instead of swapping s[i] and s[m], take out s[m], shift s[i..m-1] one place right, and put it at i. Nothing jumps over an equal record.
Solution
#include <stdio.h>
struct student { char name[20]; int marks; };
struct student s[100];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%19s %d", s[i].name, &s[i].marks);
for (int i = 0; i < n - 1; i++) {
int m = i;
for (int j = i + 1; j < n; j++)
if (s[j].marks < s[m].marks) m = j;
struct student key = s[m];
for (int k = m; k > i; k--) s[k] = s[k - 1]; /* shift, don't swap */
s[i] = key;
}
for (int i = 0; i < n; i++) printf("%s %d\n", s[i].name, s[i].marks);
return 0;
}
Input 4 / Asha 75 / Neha 75 / Ravi 60 / Priya 90:
Ravi 60
Asha 75
Neha 75
Priya 90
It is stable now, but shifting costs up to n moves per place, so it does more moves than plain selection sort.
3. Sort only the first k values. Read n k, then n values; sort the first k with insertion sort and leave the rest. If k > n, sort everything.
Solution
#include <stdio.h>
int main() {
int n, k, a[100];
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
if (k > n) k = n;
for (int i = 1; i < k; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Input 7 4 / 9 3 7 1 8 2 5:
1 3 7 9 8 2 5
Input 3 5 / 3 2 1:
1 2 3
Quick quiz
Bubble sort with the early exit on 3 1 2. What does it print?
#include <stdio.h>
int main() {
int a[] = {3, 1, 2}, n = 3;
int passes = 0, swaps = 0;
for (int pass = 0; pass < n - 1; pass++) {
int swapped = 0;
passes++;
for (int j = 0; j < n - 1 - pass; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
swaps++;
swapped = 1;
}
if (!swapped) break;
}
printf("passes %d, swaps %d\n", passes, swaps);
return 0;
}
(A) passes 2, swaps 2 (B) passes 1, swaps 2 (C) passes 2, swaps 3 (D) passes 3, swaps 2
Answer
(A). Pass 1: 3 > 1 swap, 3 > 2 swap → 1 2 3 (2 swaps). Pass 2: no swap → break. The pass with no swap still counts.
Output:
passes 2, swaps 2
Interview questions
- Why is plain bubble sort O(n²) even on sorted input? It always makes n − 1 passes. With the
swappedflag the best case is O(n). - Which of the three makes the fewest swaps? Selection sort: at most n − 1.
- Which are stable? Bubble and insertion sort (with strict
>). Selection sort is not. - Make selection sort stable. Shift instead of swapping the minimum into place (practice 2).
- Which is best for nearly sorted data? Insertion sort: close to O(n).
- Why is insertion sort used inside faster sorts for small parts? Little overhead and very fast on small or nearly sorted arrays.
- How many swaps does bubble sort make? Exactly the number of inversions.
- Why
j >= 0 && a[j] > keyand not the other way round?&&short-circuits, soa[-1](undefined behaviour) is never read. - Space complexity of all three? O(1): they sort in place.
- Why does stability matter? When sorting by a second key, a stable sort keeps the order from the first sort (for example, sort by name, then stably by marks).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Sorting | Putting values in order | 5 1 4 → 1 4 5 |
| Ascending | Smallest first | 1 2 4 5 8 |
| Descending | Biggest first | 9 7 4 3 |
| Adjacent | Next to each other | a[j] and a[j + 1] |
| Comparison | Checking which of two values is bigger | a[j] > a[j + 1] |
| Swap | Two values trade places | t = a; a = b; b = t; |
| Pass | One walk through the array, left to right | bubble sort's outer loop |
| Bubble sort | Swap out-of-order neighbours, pass after pass | Q1 |
| Dry run | Running code by hand, step by step | the pass tables above |
| Flag | A variable that remembers whether something happened | swapped |
| Early exit | Stopping a loop as soon as the answer is known | if (!swapped) break; |
| In place | Sorting inside the same array, no copy | all three sorts |
| Selection sort | Find the minimum of the rest, swap it into place | Q2 |
| Minimum index | Where the smallest value is | m |
| Record | Values that belong together | name + marks |
struct |
A C type that groups values into one record | struct student |
| Key | The value you sort by | marks |
| Stable sort | Equal keys keep their input order | Asha stays before Neha |
| Unstable sort | Equal keys may change order | selection sort |
| Insertion sort | Shift bigger values right, insert the key | Q3 |
Key value (key) |
The value being inserted in insertion sort | key = a[i] |
| Shift | Copy a value one place over | a[j + 1] = a[j] |
| Nearly sorted | Only a few values out of place | one late entry |
| Inversion | A pair i < j with a[i] > a[j] |
(5, 1) in 5 1 4 |
| Best case | The input that needs the least work | sorted input |
| Worst case | The input that needs the most work | reversed input |
| Big O | How the work grows as n grows | O(n²) |
| O(n) | Work grows in step with n | one pass |
| O(n²) | Double n, four times the work | n²/2 comparisons |
| O(1) space | A fixed amount of extra memory | t, m, key |
| Undefined behaviour (UB) | The C standard makes no promise | reading a[-1] |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | 8 seconds here |
Summary
- Bubble sort swaps out-of-order neighbours; the
swappedflag stops it after a pass with no swap: O(n) on sorted input, O(n²) worst case. - Selection sort remembers the minimum index and swaps once per place: at most n − 1 swaps, but always O(n²) comparisons, and unstable.
- Insertion sort shifts bigger values right and drops the key in: close to O(n) on nearly sorted data, O(n²) worst case, stable.
- Write
j >= 0 && a[j] > keyin that order;a[-1]is undefined behaviour. - All three sort in place with O(1) extra space.
Next episode: Sorting questions II: qsort with a comparator (and the subtraction overflow bug), sorting an array of strings, and sorting structs by two keys.