SyntaxPilot
Courses/C Coding Questions/Lesson 13
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C Coding Questions · Lesson 13 of 30

Sorting questions I

bubble sort with early exitselection sortinsertion sort; dry runsnumber of swapsstable vs unstable

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

  1. Why is plain bubble sort O(n²) even on sorted input? It always makes n − 1 passes. With the swapped flag the best case is O(n).
  2. Which of the three makes the fewest swaps? Selection sort: at most n − 1.
  3. Which are stable? Bubble and insertion sort (with strict >). Selection sort is not.
  4. Make selection sort stable. Shift instead of swapping the minimum into place (practice 2).
  5. Which is best for nearly sorted data? Insertion sort: close to O(n).
  6. Why is insertion sort used inside faster sorts for small parts? Little overhead and very fast on small or nearly sorted arrays.
  7. How many swaps does bubble sort make? Exactly the number of inversions.
  8. Why j >= 0 && a[j] > key and not the other way round? && short-circuits, so a[-1] (undefined behaviour) is never read.
  9. Space complexity of all three? O(1): they sort in place.
  10. 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 swapped flag 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] > key in 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.