These are the notes for C episode 25. It starts on results day: a register of one million roll numbers and a hundred thousand students searching it at once. The obvious search, reading from the top, can't finish. You fix it by inventing binary search from the guess-the-number game, then discover it needs sorted data, so you invent sorting: first the obvious bubble sort (too slow for 200,000 marks), then merge sort, and finally the standard library's qsort and bsearch. Along the way you meet Big-O, the way programmers describe speed. Every example was compiled with gcc -O2 -Wno-unused-result main.c -o main -lm (gcc 13, glibc 2.39, the same command as the SyntaxPilot compiler) and run as shown. The online compiler stops a program after 8 seconds and reports Time Limit Exceeded.
The problem: results day
Real-life example: board results. The board has a register of 1,000,000 students. Each student opens the results site and types a roll number; the program must find that one roll number. At 10 a.m., 100,000 students search at the same time, and the site freezes.
Searching means finding one item in a collection (or learning that it isn't there). The most obvious way is linear search: check entry 0, then 1, then 2, until one matches.
#include <stdio.h>
#define N 1000000
#define Q 10
int roll[N];
int linear(int key) {
for (int i = 0; i < N; i++)
if (roll[i] == key) return i;
return -1;
}
int main() {
for (int i = 0; i < N; i++)
roll[i] = 2 * i + 1;
int found = 0;
for (int q = 0; q < Q; q++)
if (linear(roll[N - 1 - q]) != -1) found++;
printf("Queries: %d, found: %d\n", Q, found);
return 0;
}
Queries: 10, found: 10
Roll numbers here are the odd numbers 1, 3, 5, ... in increasing order, and main searches for the students at the end of the register (the worst case for linear search). With Q = 10 it is instant. Change Q to 100000 and the online compiler stops it after 8 seconds: Time Limit Exceeded.
Why linear search is slow
- One search checks up to 1,000,000 entries.
- 100,000 searches × up to 1,000,000 checks ≈ 100 billion checks. No computer does that in 8 seconds (a rough rule: about 100 million simple steps per second).
- The register is in order, and linear search never used that. That's the clue.
The idea: guess the number
Real-life example: the guessing game. A friend thinks of a number from 1 to 100 and answers only "higher" or "lower". Nobody guesses 1, 2, 3. You guess 50: "higher!", so 1 to 50 are gone. Guess 75, the middle of what's left: "lower!", now it's 51 to 74. Always guessing the middle finds any number in at most 7 guesses (2⁷ = 128 ≥ 100). It only works because the numbers are in order.
| The game | Binary search |
|---|---|
| Numbers 1 to 100 | a sorted array |
| The lowest number still possible | lo |
| The highest number still possible | hi |
| Your guess: the middle | mid = lo + (hi - lo) / 2 |
| "Higher!" | roll[mid] < key → lo = mid + 1 |
| "Lower!" | roll[mid] > key → hi = mid - 1 |
| "Correct!" | roll[mid] == key → found |
| Nothing left to guess | lo > hi → not found |
Binary search checks the middle of the range and throws away the half that can't contain the key. Binary because every step splits what's left into two halves. 1,000,000 → 500,000 → 250,000 → ... → 1 takes about 20 halvings, so one search needs at most about 20 checks.
Sorted means arranged in order: smallest to largest (ascending) or largest to smallest (descending). Binary search only works on sorted data.
Binary search in C
#include <stdio.h>
#define N 1000000
#define Q 100000
int roll[N];
int binary(int key) {
int lo = 0, hi = N - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (roll[mid] == key) return mid;
if (roll[mid] < key) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
int main() {
for (int i = 0; i < N; i++)
roll[i] = 2 * i + 1;
int found = 0;
for (int q = 0; q < Q; q++)
if (binary(roll[N - 1 - q]) != -1) found++;
printf("Queries: %d, found: %d\n", Q, found);
printf("Roll 4 is at: %d\n", binary(4));
return 0;
}
Queries: 100000, found: 100000
Roll 4 is at: -1
The same 100,000 searches that timed out finish instantly: about 100,000 × 20 = 2 million checks instead of 100 billion. Roll 4 doesn't exist (all roll numbers are odd), so binary(4) correctly returns -1.
Why mid = lo + (hi - lo) / 2?
(lo + hi) / 2 gives the same middle, but on a huge array lo + hi can pass INT_MAX (2,147,483,647) and overflow into a negative number. hi - lo always fits, so lo + (hi - lo) / 2 is the safe habit. This exact bug sat in Java's library binary search for about nine years before it was found in 2006.
Binary search's famous bug: lo = mid
A version many people write leaves out the + 1 and - 1:
#include <stdio.h>
int a[] = {11, 23, 35, 47, 59};
int find(int key) {
int lo = 0, hi = 4;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == key) return mid;
if (a[mid] < key) lo = mid;
else hi = mid;
}
return -1;
}
int main() {
printf("47 is at index %d\n", find(47));
return 0;
}
47 is at index 3
Correct, so it looks fine. Change both 47s to 59 (the last item) and the program never finishes: Time Limit Exceeded on a five-item array.
Trace it:
lo |
hi |
mid |
a[mid] |
Action |
|---|---|---|---|---|
| 0 | 4 | 2 | 35 < 59 | lo = 2 |
| 2 | 4 | 3 | 47 < 59 | lo = 3 |
| 3 | 4 | 3 | 47 < 59 | lo = 3 (no change!) |
| 3 | 4 | 3 | 47 < 59 | lo = 3 ... forever |
When mid == lo, lo = mid changes nothing. mid was already checked, so skip it: lo = mid + 1 and hi = mid - 1. Rule: every step must make the range smaller.
The next problem: data arrives unsorted
Answer sheets are handed in in any order; orders arrive in the order customers click. Binary search on a messy pile is useless: "higher" or "lower" says nothing about which half to drop. So first we sort: arrange the items in order. Sort once, then search as many times as you like.
Three ways people sort
| In real life | Sorting method | Idea |
|---|---|---|
| School assembly line: if a taller child stands in front of a shorter one, they swap; repeat until nobody swaps | Bubble sort | compare neighbours, swap if out of order |
| Picking a cricket team: choose the best player left, again and again | Selection sort | select the smallest remaining item, put it next |
| Arranging playing cards in your hand: slide each new card into place | Insertion sort | insert each item into the already-sorted part |
A comparison is one check of two items ("is this one bigger than that one?"). A swap means two items exchange places, using a temporary variable.
Bubble sort
#include <stdio.h>
#include <stdlib.h>
#define N 10
int marks[N];
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
int main() {
srand(7);
for (int i = 0; i < N; i++)
marks[i] = rand() % 100;
bubble_sort(marks, N);
for (int i = 0; i < 10; i++)
printf("%d ", marks[i]);
printf("\n");
return 0;
}
0 25 43 53 71 77 86 97 99 99
srand(7) fixes the random sequence, so rand() % 100 gives the same ten marks (0 to 99) every run. Each pass of the inner loop compares neighbours a[j] and a[j + 1] and swaps them if they're in the wrong order, which carries the biggest remaining value to the end, like a bubble rising. The outer loop repeats the pass n - 1 times; the - i skips the end of the array, which is already sorted.
Now change N to 200000 (a whole state's answer sheets): Time Limit Exceeded.
Why bubble sort is slow
- Pass 1 makes
n - 1comparisons, pass 2 makesn - 2, ... in total about n × n / 2. - n = 200,000 → about 20 billion comparisons.
- Double n → four times the work. Timing the same program on our machine:
| n | bubble sort time |
|---|---|
| 10,000 | 0.23 s |
| 20,000 | 1.07 s |
| 40,000 | 4.96 s |
| 200,000 | Time Limit Exceeded |
Selection sort and insertion sort grow the same way (n × n). They're fine for small inputs (insertion sort is even fast on data that's almost sorted), but not for a state's results.
Merge sort: two sorted piles
Real-life example: an exam hall. Too many answer sheets? Split the pile in half and give each half to a different teacher. Each teacher does the same with their half, until a pile has one sheet (already sorted). Then merging two sorted piles is easy: look at the top sheet of each pile, take the smaller one, repeat. Each sheet is looked at once.
#include <stdio.h>
#include <stdlib.h>
#define N 200000
int marks[N], tmp[N];
void merge_sort(int a[], int lo, int hi) {
if (hi - lo < 2) return;
int mid = lo + (hi - lo) / 2;
merge_sort(a, lo, mid);
merge_sort(a, mid, hi);
int i = lo, j = mid, k = lo;
while (i < mid && j < hi)
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i < mid) tmp[k++] = a[i++];
while (j < hi) tmp[k++] = a[j++];
for (k = lo; k < hi; k++) a[k] = tmp[k];
}
int main() {
srand(7);
for (int i = 0; i < N; i++)
marks[i] = rand() % 100;
merge_sort(marks, 0, N);
printf("Lowest: %d, highest: %d\n", marks[0], marks[N - 1]);
return 0;
}
Lowest: 0, highest: 99
The same 200,000 marks that bubble sort couldn't finish are sorted in about 0.02 seconds.
How it works:
merge_sort(a, lo, hi)sortsa[lo]up to, but not including,a[hi]. Fewer than two items: already sorted, return.- Split at
midand sort each half by callingmerge_sortitself. A function that calls itself is recursion (episode 27 is all about it); for now, trust that each half comes back sorted. - Merge:
iwalks the left pile,jthe right pile; copy the smaller top intotmp. When one pile runs out, copy the rest of the other. Then copytmpback intoa. a[i] <= a[j]takes from the left pile on a tie, so equal items keep their original order: merge sort is stable.
Why it's fast: halving 200,000 items reaches piles of one after about 18 levels, and each level looks at every item once: about 18 × 200,000 ≈ 3.6 million steps instead of 20 billion. Its price is the extra tmp array (O(n) extra memory).
Big-O in plain words
Big-O describes how the work grows when the data grows. It doesn't give seconds; it gives the shape of the growth. n is the number of items, and log n (log base 2) is how many times you can halve n before you reach 1 (log 1,000,000 ≈ 20).
| Big-O | Name | Example from today | Work for n = 1,000,000 |
|---|---|---|---|
| O(1) | constant | a[k], one comparison |
1 |
| O(log n) | logarithmic | binary search | about 20 |
| O(n) | linear | linear search | 1,000,000 |
| O(n log n) | "n log n" | merge sort, qsort |
about 20,000,000 |
| O(n²) | quadratic | bubble, selection, insertion sort | 1,000,000,000,000 |
At roughly 100 million simple steps per second, O(n²) on a million items takes hours; O(n log n) takes a fraction of a second.
| Algorithm | Best | Average | Worst | Extra memory | Stable |
|---|---|---|---|---|---|
| Linear search | O(1) | O(n) | O(n) | O(1) | - |
| Binary search (sorted data) | O(1) | O(log n) | O(log n) | O(1) | - |
| Bubble sort | O(n) with an early-exit check, O(n²) as written | O(n²) | O(n²) | O(1) | yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | no |
| Insertion sort | O(n) (already sorted) | O(n²) | O(n²) | O(1) | yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | yes |
qsort |
not specified by the C standard; in practice O(n log n) | not guaranteed |
qsort: the library sort
You don't have to write a sort every time. stdlib.h declares:
void qsort(void *base, size_t count, size_t size,
int (*compar)(const void *, const void *));
You pass the array, how many items, the size of one item, and a comparator: your function that compares two items. Because qsort works on any type, it hands the comparator two void * pointers: addresses with no type.
The obvious comparator reads through them directly:
int cmp(const void *a, const void *b) {
return *a - *b;
}
main.c: In function 'cmp':
main.c:8:12: warning: dereferencing 'void *' pointer
main.c:8:12: error: void value not ignored as it ought to be
A void * doesn't know what it points to, so C can't read a number through it. Cast each one to const int * first:
#include <stdio.h>
#include <stdlib.h>
#define N 200000
int marks[N];
int cmp(const void *a, const void *b) {
int x = *(const int *)a;
int y = *(const int *)b;
return x - y;
}
int main() {
srand(7);
for (int i = 0; i < N; i++)
marks[i] = rand() % 100;
qsort(marks, N, sizeof(int), cmp);
printf("Lowest: %d, highest: %d\n", marks[0], marks[N - 1]);
return 0;
}
Lowest: 0, highest: 99
The comparator's contract
cmp(a, b) returns |
Meaning |
|---|---|
| negative | a goes before b |
| zero | equal |
| positive | a goes after b |
qsort looks only at the sign. Compare y against x instead to sort largest first. The same qsort sorts students, prices, names, anything: you decide what "bigger" means.
The x - y overflow trap
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
int x = *(const int *)a;
int y = *(const int *)b;
return x - y;
}
int main() {
int bal[] = {2000000000, -2000000000, 7};
qsort(bal, 3, sizeof(int), cmp);
for (int i = 0; i < 3; i++)
printf("%d\n", bal[i]);
return 0;
}
2000000000
-2000000000
7
Not sorted! 2000000000 - (-2000000000) is 4,000,000,000, which doesn't fit in an int (max 2,147,483,647). Signed overflow is undefined behaviour in C; here it wrapped to a negative number, so qsort was told that 2,000,000,000 is the smaller one. The safe comparator:
return (x > y) - (x < y);
-2000000000
7
2000000000
Each comparison is 1 or 0, so the result is always -1, 0 or 1, with no subtraction of big numbers. x - y is only safe when you know the values are small (like marks from 0 to 100).
bsearch: the library binary search
void *bsearch(const void *key, const void *base, size_t count, size_t size,
int (*compar)(const void *, const void *));
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
int x = *(const int *)a;
int y = *(const int *)b;
return (x > y) - (x < y);
}
int main() {
int roll[] = {105, 101, 108, 103, 102};
int n = 5, key = 103;
qsort(roll, n, sizeof(int), cmp);
int *p = bsearch(&key, roll, n, sizeof(int), cmp);
if (p != NULL)
printf("Found %d at index %d\n", *p, (int)(p - roll));
else
printf("%d not found\n", key);
return 0;
}
Found 103 at index 2
bsearch takes the address of the key, the array, the count, the item size and the same comparator the array was sorted with. It returns a pointer to a matching item, or NULL. p - roll turns the pointer into an index (pointer arithmetic, episode 11).
Comment out the qsort line and run again:
103 not found
103 is in the array, but bsearch assumes the data is sorted with that comparator. No error, no warning: just a wrong answer. If several items are equal, bsearch may return any one of them.
Mini project: results lookup and rank list
#include <stdio.h>
#include <stdlib.h>
struct student { int roll; char name[10]; int marks; };
int by_roll(const void *a, const void *b) {
const struct student *x = a, *y = b;
return (x->roll > y->roll) - (x->roll < y->roll);
}
int by_marks(const void *a, const void *b) {
const struct student *x = a, *y = b;
if (x->marks != y->marks)
return (y->marks > x->marks) ? 1 : -1;
return by_roll(a, b); // tie: smaller roll first
}
int main() {
struct student s[] = {{104, "Meera", 88}, {101, "Aman", 72},
{105, "Ravi", 95}, {102, "Sana", 88}, {103, "Kabir", 64}};
int n = 5;
qsort(s, n, sizeof s[0], by_roll);
struct student key = {103};
struct student *p = bsearch(&key, s, n, sizeof s[0], by_roll);
if (p != NULL)
printf("Roll %d: %s, %d marks\n", p->roll, p->name, p->marks);
qsort(s, n, sizeof s[0], by_marks);
for (int i = 0; i < n; i++)
printf("Rank %d: %-6s %d\n", i + 1, s[i].name, s[i].marks);
return 0;
}
Roll 103: Kabir, 64 marks
Rank 1: Ravi 95
Rank 2: Sana 88
Rank 3: Meera 88
Rank 4: Aman 72
Rank 5: Kabir 64
by_rollcompares two students by roll number, safely. Thevoid *parameters convert toconst struct student *without a cast in C.- To look someone up, fill only the field the comparator reads:
struct student key = {103};(the other fields become 0). by_marksputs higher marks first, and on equal marks falls back toby_roll: a tie-break. Sana and Meera both have 88; Sana is first because roll 102 < 104.%-6sprints the name left-aligned in 6 characters, so the marks line up.
Stable sorting and ties
A sort is stable if equal items keep the order they had before sorting. Merge sort (with <=) and insertion sort are stable; selection sort is not. The C standard does not promise that qsort is stable, so the order of ties could differ between compilers or library versions. If the order of ties matters (a rank list, a leaderboard), say it in the comparator with a tie-break.
Common mistakes (and the real messages)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
return *a - *b; with const void *a, *b |
error: void value not ignored as it ought to be (and warning: dereferencing 'void *' pointer) |
A void * has no type to read |
int x = *(const int *)a; |
return x - y; with big values |
No error: wrong order (2000000000 before -2000000000) |
x - y overflows an int |
return (x > y) - (x < y); |
lo = mid; / hi = mid; in binary search |
Time Limit Exceeded (searching 59 in a 5-item array) | The range stops shrinking when mid == lo |
lo = mid + 1; / hi = mid - 1; |
bsearch on unsorted data |
No error: 103 not found |
Binary search needs data sorted with the same comparator | qsort first, with the same comparator |
Comparator with the wrong signature, int cmp(int *a, int *b) |
warning: passing argument 4 of 'qsort' from incompatible pointer type [-Wincompatible-pointer-types] (an error in gcc 14) |
qsort expects int (*)(const void *, const void *) |
Take const void * and cast inside |
Forgetting #include <stdlib.h> |
warning: implicit declaration of function 'qsort' [-Wimplicit-function-declaration] (an error in gcc 14) |
qsort/bsearch are declared there |
#include <stdlib.h> |
mid = (lo + hi) / 2 on huge arrays |
Wrong index or a crash | lo + hi overflows |
mid = lo + (hi - lo) / 2 |
| Bubble/insertion sort on 200,000 items | Time Limit Exceeded | O(n²): about 20 billion comparisons | qsort or merge sort, O(n log n) |
Practice
- Search students by name: sort with a comparator that uses
strcmp(episode 9), thenbsearchwith the same comparator. - Write insertion sort (the playing-cards method) and time it on 50,000 random marks.
- In a sorted array with repeated values, find the first index of a key with binary search (
bsearchmay return any of the equal ones). - Sort prices largest first with
qsort.
Solutions
All four, verified together:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct student { int roll; char name[10]; int marks; };
int by_name(const void *a, const void *b) {
const struct student *x = a, *y = b;
return strcmp(x->name, y->name);
}
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int card = a[i], j = i - 1;
while (j >= 0 && a[j] > card) { // shift bigger cards right
a[j + 1] = a[j];
j--;
}
a[j + 1] = card; // drop the card into the gap
}
}
int first_of(const int a[], int n, int key) {
int lo = 0, hi = n - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < key) lo = mid + 1;
else {
if (a[mid] == key) ans = mid; // remember it, keep looking left
hi = mid - 1;
}
}
return ans;
}
int desc(const void *a, const void *b) {
int x = *(const int *)a, y = *(const int *)b;
return (y > x) - (y < x);
}
int main() {
struct student s[] = {{104, "Meera", 88}, {101, "Aman", 72},
{105, "Ravi", 95}, {102, "Sana", 88}, {103, "Kabir", 64}};
int n = 5;
qsort(s, n, sizeof s[0], by_name);
struct student key;
strcpy(key.name, "Ravi");
struct student *p = bsearch(&key, s, n, sizeof s[0], by_name);
if (p != NULL)
printf("%s: roll %d, %d marks\n", p->name, p->roll, p->marks);
int cards[] = {7, 2, 9, 4, 1};
insertion_sort(cards, 5);
for (int i = 0; i < 5; i++) printf("%d ", cards[i]);
printf("\n");
int m[] = {35, 47, 47, 47, 59, 72};
printf("First 47 at index %d\n", first_of(m, 6, 47));
printf("First 50 at index %d\n", first_of(m, 6, 50));
int price[] = {120, 15, 999, 450, 60};
qsort(price, 5, sizeof(int), desc);
for (int i = 0; i < 5; i++) printf("%d ", price[i]);
printf("\n");
return 0;
}
Ravi: roll 105, 95 marks
1 2 4 7 9
First 47 at index 1
First 50 at index -1
999 450 120 60 15
2 (timing). The same insertion_sort on 50,000 random marks (srand(7), rand() % 100) took about 0.24 s on our machine and printed Lowest: 0, highest: 99. Try 100,000 and 200,000: the time roughly quadruples each time n doubles (O(n²)), while qsort stays instant.
3. When a[mid] == key, don't return: remember mid as an answer and keep searching the left half (hi = mid - 1). The last remembered answer is the first occurrence. Still O(log n).
Quick quiz
// a sorted array of 1,000 roll numbers
// binary search for a roll number
// that is NOT in the array
// at most how many times does the loop
// compare roll[mid] with the key?
- A.
10 - B.
100 - C.
500 - D.
1,000
Answer
A: about 10. Each check halves the range: 1,000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1. Ten halvings, because 2¹⁰ = 1,024 ≥ 1,000. Linear search would need all 1,000 checks.
Interview questions
- What is the difference between linear search and binary search? What does binary search require?
- Write binary search. Why
lo <= hi,lo = mid + 1andhi = mid - 1? What goes wrong withlo = mid? - Why is
mid = lo + (hi - lo) / 2preferred over(lo + hi) / 2? - What are the time complexities of bubble, selection, insertion and merge sort? Which are stable?
- When is insertion sort a good choice? (Small or almost-sorted data: it's O(n) on sorted input.)
- Explain merge sort. What extra memory does it need?
- What does Big-O notation describe? What is O(log n) in plain words?
- How do you use
qsortandbsearch? What must the comparator return? - Why is
return a - b;a dangerous comparator? - Is
qsortstable? How do you get a fixed order for equal items? - Find the first and last position of a value in a sorted array in O(log n).
- Sort once and search many times, or search linearly every time? (With many searches, sorting first wins: O(n log n + q log n) vs O(q × n).)
Glossary
| Term | Meaning | Example |
|---|---|---|
| Searching | Finding one item in a collection, or learning it isn't there | find roll 103 |
| Linear search | Check every item from the start until one matches | for (i = 0; i < N; i++) if (roll[i] == key) ... |
| Binary search | On sorted data, check the middle and drop the half that can't contain the key | lo, mid, hi |
| Sorted | Arranged in order: ascending (smallest first) or descending (largest first) | 11 23 35 47 59 |
| Sorting | Rearranging items into order | bubble sort, merge sort, qsort |
lo, hi, mid |
First and last positions still possible, and the middle one being checked | mid = lo + (hi - lo) / 2 |
| Comparison | One check of two items: which is bigger? | a[j] > a[j + 1] |
| Swap | Two items exchange places | t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; |
| Pass | One trip through the array in bubble sort | the inner j loop |
| Bubble sort | Repeatedly swap neighbours that are out of order | O(n²) |
| Selection sort | Repeatedly select the smallest remaining item | O(n²) |
| Insertion sort | Insert each item into the already-sorted part, like cards in a hand | O(n²), O(n) if almost sorted |
| Merge sort | Split in halves, sort each half, merge the two sorted halves | O(n log n) |
| Merge | Combine two sorted lists by repeatedly taking the smaller front item | two piles of answer sheets |
| Recursion | A function that calls itself (episode 27) | merge_sort(a, lo, mid); |
| Big-O | How the work grows when the input size n grows | O(n), O(log n), O(n²) |
| O(log n) | Work grows by one step each time n doubles | binary search: 1,000,000 → 20 steps |
| O(n²) | Doubling n makes four times the work | bubble sort |
| Time Limit Exceeded | The online compiler stopped a program that ran longer than 8 seconds | bubble sort on 200,000 marks |
qsort |
The standard library's sort, from stdlib.h |
qsort(a, n, sizeof(int), cmp); |
bsearch |
The standard library's binary search; returns a pointer or NULL |
bsearch(&key, a, n, sizeof(int), cmp) |
| Comparator | Your function that tells qsort/bsearch how two items compare: negative, zero or positive |
int cmp(const void *a, const void *b) |
void * |
A pointer with no type; must be cast before reading | *(const int *)a |
| Integer overflow | A result too big for its type; for signed int it's undefined behaviour |
2000000000 - (-2000000000) |
| Stable sort | Equal items keep their original order | merge sort with <= |
| Tie-break | A second rule in the comparator for equal items | equal marks → smaller roll first |
srand / rand |
Seed and generate pseudo-random numbers (stdlib.h) |
srand(7); rand() % 100 |
Summary
- Linear search checks every item: O(n). Fine once, Time Limit Exceeded for 100,000 searches in a million items.
- Binary search keeps
lo,hiand checksmid = lo + (hi - lo) / 2, dropping half each step: O(log n), about 20 checks for a million items. It needs sorted data, and every step must shrink the range (mid + 1,mid - 1). - Bubble, selection and insertion sort are O(n²): fine for small data, Time Limit Exceeded for 200,000 items.
- Merge sort splits, sorts each half and merges two sorted piles: O(n log n), and stable.
- Big-O describes how the work grows with the data: O(1) < O(log n) < O(n) < O(n log n) < O(n²).
qsortsorts anything with a comparator that returns negative, zero or positive; cast thevoid *pointers, and use(x > y) - (x < y), notx - y.qsortisn't guaranteed stable, so add a tie-break when ties matter.bsearchneeds data sorted with the same comparator; on unsorted data it silently gives wrong answers.
Next episode: Memory bugs and how to find them: sanitizers and valgrind, the tools that catch the bugs C stays silent about.