These are the notes for C Coding Questions, episode 14, placement practice for people who finished the SyntaxPilot C course. Sorting questions, part two: sorting fast with qsort and a comparator (and the famous a - b overflow), sorting an array of strings with strcmp, and sorting structs by two keys with a tie-breaker.
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, glibc, 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. The programs print a space after every number or name, so each output line ends with a space.
Real-life pictures
| In real life | In C |
|---|---|
| a board result with 200,000 roll numbers: a clerk sorts, you only give the rule | qsort + a comparator |
| a class register in alphabetical order | sorting strings with strcmp |
| a merit list: marks high to low, same marks in alphabetical order | sorting structs by two keys (a tie-breaker) |
Q1: Sort 200,000 numbers fast
Problem. Read n integers (n up to 200,000) and print them smallest first.
| Input | Output |
|---|---|
30 10 50 20 40 |
10 20 30 40 50 |
2000000000 -2000000000 0 5 -7 |
-2000000000 -7 0 5 2000000000 |
3 1 3 -1 0 1 |
-1 0 1 1 3 3 |
42 |
42 |
| 200,000 numbers in reverse order | in 8 seconds |
Edge cases: a big n, repeated values, negative numbers, values close to INT_MAX (2,147,483,647) and INT_MIN (−2,147,483,648).
The obvious attempt: bubble sort
Last episode's bubble sort: compare neighbours, swap them when they are in the wrong order, repeat. The test fills the array with n, n-1, ..., 1, the worst case.
#include <stdio.h>
int a[200000];
void 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() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) a[i] = n - i;
sort(a, n);
printf("first %d, last %d\n", a[0], a[n - 1]);
return 0;
}
Input 200000:
Time Limit Exceeded
Why. Bubble sort compares about n² / 2 pairs: for n = 200,000 that is 20 billion comparisons. It is O(n²).
The fix: qsort from <stdlib.h>
The C library already has a fast general sort:
void qsort(void *base, size_t n, size_t size, int (*cmp)(const void *, const void *));
| Argument | Meaning | Here |
|---|---|---|
base |
the start of the array | a |
n |
how many elements | n |
size |
bytes in one element | sizeof(int) or sizeof(a[0]) |
cmp |
the comparator: the rule that says which of two elements comes first | cmp |
size_t is the unsigned integer type that sizeof gives. glibc's qsort (the one here) does about n log n comparisons: for 200,000 numbers about 3.5 million, not 20 billion. (The C standard does not say which algorithm qsort uses, how fast it is, or that it is stable; glibc's is O(n log n).)
The comparator. qsort calls it with two pointers, a and b, each pointing at one element of the array:
const void *is a pointer to anything (void *) that the function promises only to read (const).qsortdoes not know whether you sort ints, names or students, so it hands you untyped pointers.- Turn it back into the real type and read it:
*(const int *)a. - Return a negative number if
ashould come first, 0 if they are equal, a positive number ifbshould come first.
The comparator everyone writes first: a - b
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return *(const int *)a - *(const int *)b;
}
int a[200000];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) a[i] = n - i;
qsort(a, n, sizeof(int), cmp);
printf("first %d, last %d\n", a[0], a[n - 1]);
return 0;
}
Input 200000:
first 1, last 200000
Instant. The same comparator, reading the numbers from the input:
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return *(const int *)a - *(const int *)b;
}
int main() {
int n, a[100];
scanf("%d", &n);
if (n < 0 || n > 100) {
printf("n must be 0 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
qsort(a, n, sizeof(int), cmp);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Input 5 / 30 10 50 20 40:
10 20 30 40 50
Input 5 / 2000000000 -2000000000 0 5 -7:
-7 0 5 2000000000 -2000000000
The smallest number, −2,000,000,000, is printed last.
Why. 2000000000 - (-2000000000) is 4,000,000,000, which is bigger than INT_MAX. That is signed overflow, which is undefined behaviour (UB: the C standard makes no promise about what happens). Here it wrapped around to −294,967,296, a negative number, so qsort was told that 2,000,000,000 is smaller than −2,000,000,000.
The fix: return only the sign
The comparator only needs the sign, not the difference. x > y is 1 or 0 and x < y is 1 or 0, so (x > y) - (x < y) is 1, 0 or −1, and it can never overflow.
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
int x = *(const int *)a, y = *(const int *)b;
return (x > y) - (x < y);
}
int main() {
int n, a[100];
scanf("%d", &n);
if (n < 0 || n > 100) {
printf("n must be 0 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
qsort(a, n, sizeof(int), cmp);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
| Input | Output |
|---|---|
5 / 2000000000 -2000000000 0 5 -7 |
-2000000000 -7 0 5 2000000000 |
6 / 3 1 3 -1 0 1 |
-1 0 1 1 3 3 |
1 / 42 |
42 |
0 |
an empty line |
Complexity. Time: about n log n comparisons. Space: glibc's qsort may use extra memory inside, up to about n elements; the comparator itself uses O(1).
Q2: Sort names alphabetically
Problem. Read n names (one word each, up to 20 letters) and print them in alphabetical order.
| Input | Output |
|---|---|
Ravi Asha Neha Kiran Priya |
Asha Kiran Neha Priya Ravi |
neha Asha Ravi asha |
Asha Ravi asha neha |
Ravi Asha Ravi |
Asha Ravi Ravi |
Edge cases: the same name twice, capital vs small letters, n = 0.
The names are read into buf (a 2D char array, one row per name), and name is an array of pointers: name[i] points at row i. Sorting the pointers is cheap: qsort moves 8-byte pointers, never the letters.
The obvious attempt: pass strcmp straight to qsort
strcmp(s, t) compares two strings letter by letter and returns negative, zero or positive, just like a comparator. So why not pass it directly?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
int n;
char buf[100][21], *name[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%20s", buf[i]);
name[i] = buf[i];
}
qsort(name, n, sizeof(char *), strcmp);
for (int i = 0; i < n; i++) printf("%s ", name[i]);
printf("\n");
return 0;
}
The compiler warns:
main.c: In function ‘main’:
main.c:13:36: warning: passing argument 4 of ‘qsort’ from incompatible pointer type [-Wincompatible-pointer-types]
13 | qsort(name, n, sizeof(char *), strcmp);
| ^~~~~~
| |
| int (*)(const char *, const char *)
In file included from main.c:2:
/usr/include/stdlib.h:971:34: note: expected ‘__compar_fn_t’ {aka ‘int (*)(const void *, const void *)’} but argument is of type ‘int (*)(const char *, const char *)’
971 | __compar_fn_t __compar) __nonnull ((1, 4));
| ~~~~~~~~~~~~~~^~~~~~~~
Input 5 / Ravi Asha Neha Kiran Priya (one real run):
Ravi Asha Neha Kiran Priya
Not alphabetical. Other runs printed other orders, for example Kiran Priya Ravi Asha Neha and Priya Ravi Asha Neha Kiran.
Why. qsort always passes pointers to the elements. Each element of name is already a char *, so the comparator receives &name[i], a char ** (a pointer to a pointer). strcmp treated that as the name and compared the bytes of the addresses. Calling a function through a pointer of the wrong type is undefined behaviour, and since the addresses change from run to run (address space layout randomization), so does the order. The -Wincompatible-pointer-types warning was telling us exactly this. (Newer gcc, version 14 and later, makes it an error.)
The fix: a wrapper comparator
Cast a to char *const * (a pointer to a read-only char *), dereference it once, and you have the name:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare_names(const void *a, const void *b) {
const char *x = *(char *const *)a;
const char *y = *(char *const *)b;
return strcmp(x, y);
}
int main() {
int n;
char buf[100][21], *name[100];
scanf("%d", &n);
if (n < 0 || n > 100) {
printf("n must be 0 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) {
scanf("%20s", buf[i]);
name[i] = buf[i];
}
qsort(name, n, sizeof(char *), compare_names);
for (int i = 0; i < n; i++) printf("%s ", name[i]);
printf("\n");
return 0;
}
| Input | Output |
|---|---|
5 / Ravi Asha Neha Kiran Priya |
Asha Kiran Neha Priya Ravi |
4 / neha Asha Ravi asha |
Asha Ravi asha neha |
3 / Ravi Asha Ravi |
Asha Ravi Ravi |
0 |
an empty line |
No warning. Capital letters come first because strcmp compares character codes (ASCII): 'A' is 65 and 'a' is 97, and every capital letter is smaller than every small letter. To ignore case, compare tolower of each letter (practice question 2).
If the names are stored in a 2D array
char names[100][21]and you sort the rows themselves,qsort(names, n, sizeof(names[0]), cmp)passes pointers to rows, and thenreturn strcmp((const char *)a, (const char *)b);is right, because each element is the characters themselves. Know what one element is.
Complexity. Time: about n log n comparisons, each reading up to the length L of a name: O(n log n · L). Space: the array of pointers; qsort moves only pointers.
Q3: A merit list (sort structs by two keys)
Problem. Read n students, each a name and marks, and print them by marks, highest first; students with the same marks in alphabetical order of name.
A struct (structure) groups related values under one name: struct Student { char name[21]; int marks; };. The key is the value we sort by: marks is the first key, the name is the second key, the tie-breaker used only when the first keys are equal.
| Input | Output |
|---|---|
Ravi 80, Asha 90, Neha 80, Kiran 90, Priya 70 |
Asha 90, Kiran 90, Neha 80, Ravi 80, Priya 70 |
Ravi 60, Rahul 50, Asha 60, Neha 60 |
Asha 60, Neha 60, Ravi 60, Rahul 50 |
Asha 75 |
Asha 75 |
Edge cases: all marks equal, one student, n = 0.
The obvious attempt: sort by marks only
The comparator receives pointers to two students, p and q. Comparing q's marks with p's (the other way round) puts higher marks first. p->marks (the arrow operator) reads the field marks through the pointer p; it is (*p).marks.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Student {
char name[21];
int marks;
};
int cmp(const void *a, const void *b) {
const struct Student *p = a, *q = b;
return (q->marks > p->marks) - (q->marks < p->marks);
}
int main() {
int n;
struct Student s[100];
scanf("%d", &n);
if (n < 0 || n > 100) {
printf("n must be 0 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%20s %d", s[i].name, &s[i].marks);
qsort(s, n, sizeof(struct Student), cmp);
for (int i = 0; i < n; i++) printf("%s %d\n", s[i].name, s[i].marks);
return 0;
}
Input 5 / Ravi 80 / Asha 90 / Neha 80 / Kiran 90 / Priya 70:
Asha 90
Kiran 90
Ravi 80
Neha 80
Priya 70
Ravi 80 comes before Neha 80, but N comes before R.
Why. For Ravi and Neha the comparator returns 0 (equal), so qsort may put them in either order. Here it kept the input order. A sort is stable if it keeps equal elements in their input order; the C standard does not promise that qsort is stable, so you cannot rely on the order of ties at all.
The fix: a tie-breaker inside the comparator
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Student {
char name[21];
int marks;
};
int cmp(const void *a, const void *b) {
const struct Student *p = a, *q = b;
if (p->marks != q->marks)
return (q->marks > p->marks) - (q->marks < p->marks);
return strcmp(p->name, q->name);
}
int main() {
int n;
struct Student s[100];
scanf("%d", &n);
if (n < 0 || n > 100) {
printf("n must be 0 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%20s %d", s[i].name, &s[i].marks);
qsort(s, n, sizeof(struct Student), cmp);
for (int i = 0; i < n; i++) printf("%s %d\n", s[i].name, s[i].marks);
return 0;
}
| Input | Output |
|---|---|
5 / Ravi 80 / Asha 90 / Neha 80 / Kiran 90 / Priya 70 |
Asha 90, Kiran 90, Neha 80, Ravi 80, Priya 70 |
4 / Ravi 60 / Rahul 50 / Asha 60 / Neha 60 |
Asha 60, Neha 60, Ravi 60, Rahul 50 |
1 / Asha 75 |
Asha 75 |
0 |
(nothing) |
Complexity. Time: about n log n comparisons. Space: qsort moves whole structs (28 bytes each here); for big structs, sort an array of pointers to them instead.
Complexity summary
| Task | Method | Time | Space |
|---|---|---|---|
| sort n ints | bubble sort | O(n²): Time Limit Exceeded for 200,000 | O(1) |
qsort + a - b |
O(n log n), wrong for big values (UB) | up to O(n) inside qsort | |
qsort + (x > y) - (x < y) |
O(n log n) | up to O(n) inside qsort | |
| sort n names | qsort(..., strcmp) |
wrong (UB), a warning | — |
qsort + compare_names wrapper |
O(n log n · L) | the pointer array | |
| merit list | marks only | O(n log n), ties in no fixed order | |
| marks, then name | O(n log n · L) | moves whole structs |
A comparator must also be consistent: the same two elements must always give the same answer, and if a comes before b and b before c, a must come before c. Otherwise qsort's result is undefined.
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| bubble sort for 200,000 numbers | Time Limit Exceeded |
O(n²): 20 billion comparisons | qsort |
return *(int *)a - *(int *)b; |
no error: -7 0 5 2000000000 -2000000000 |
a - b overflows int (UB) |
(x > y) - (x < y) |
qsort(name, n, sizeof(char *), strcmp); |
warning: passing argument 4 of 'qsort' from incompatible pointer type [-Wincompatible-pointer-types], names not sorted |
the comparator gets a char ** |
a wrapper: *(char *const *)a |
strcmp((const char *)a, (const char *)b) on an array of char * |
no warning, names not sorted | a points at a pointer, not at letters |
dereference once |
qsort(a, n, sizeof(a), cmp); |
no warning: memory overwritten (UB) | the size of the whole array, not one element | sizeof(a[0]) |
| comparing only the first key | ties in the wrong order | 0 means "any order", qsort is not stable | a tie-breaker in the comparator |
a comparator that returns only 0 or 1 (return x > y;) |
wrong order | it never says "a first" | return negative, zero or positive |
Here is the "cast to char *" mistake for real. It compiles with no warning:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare_names(const void *a, const void *b) {
return strcmp((const char *)a, (const char *)b);
}
int main() {
char buf[5][21] = {"Ravi", "Asha", "Neha", "Kiran", "Priya"};
char *name[5];
for (int i = 0; i < 5; i++) name[i] = buf[i];
qsort(name, 5, sizeof(char *), compare_names);
for (int i = 0; i < 5; i++) printf("%s ", name[i]);
printf("\n");
return 0;
}
Output (one real run; it changes from run to run, like Q2's first attempt):
Priya Ravi Asha Neha Kiran
Your turn: by length, then alphabetically (solution)
Problem. Read n names and print them shortest first; names of the same length in alphabetical order. Ravi Asha Priya Rahul Neha → Asha Neha Ravi Priya Rahul.
Idea. Q2's wrapper to get the names, then Q3's tie-breaker: compare the lengths (strlen, with the safe sign trick, since size_t is unsigned and lx - ly would wrap), and on a tie return strcmp.
Show the solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int bylen(const void *a, const void *b) {
const char *x = *(char *const *)a;
const char *y = *(char *const *)b;
size_t lx = strlen(x), ly = strlen(y);
if (lx != ly) return (lx > ly) - (lx < ly);
return strcmp(x, y);
}
int main() {
int n;
char buf[100][21], *name[100];
scanf("%d", &n);
if (n < 0 || n > 100) {
printf("n must be 0 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) {
scanf("%20s", buf[i]);
name[i] = buf[i];
}
qsort(name, n, sizeof(char *), bylen);
for (int i = 0; i < n; i++) printf("%s ", name[i]);
printf("\n");
return 0;
}
Input 5 / Ravi Asha Priya Rahul Neha:
Asha Neha Ravi Priya Rahul
Input 3 / Kiran Asha Kiran:
Asha Kiran Kiran
Practice questions (with solutions)
1. Sort in descending order. Swap the two comparisons: (x < y) - (x > y). Never write y - x, which overflows just like x - y.
Solution
#include <stdio.h>
#include <stdlib.h>
int desc(const void *a, const void *b) {
int x = *(const int *)a, y = *(const int *)b;
return (x < y) - (x > y);
}
int main() {
int a[] = {5, -2000000000, 9, 2000000000, 0};
int n = sizeof(a) / sizeof(a[0]);
qsort(a, n, sizeof(a[0]), desc);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Output:
2000000000 9 5 0 -2000000000
2. Sort names ignoring capital letters. Compare tolower of each letter (from <ctype.h>, with a cast to unsigned char). strcasecmp exists on Linux, but it is POSIX, not standard C.
Solution
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
int cmpnocase(const void *a, const void *b) {
const char *x = *(char *const *)a;
const char *y = *(char *const *)b;
while (*x && tolower((unsigned char)*x) == tolower((unsigned char)*y)) {
x++;
y++;
}
return tolower((unsigned char)*x) - tolower((unsigned char)*y);
}
int main() {
char *name[] = {"neha", "Asha", "Ravi", "asha", "kiran"};
int n = sizeof(name) / sizeof(name[0]);
qsort(name, n, sizeof(char *), cmpnocase);
for (int i = 0; i < n; i++) printf("%s ", name[i]);
printf("\n");
return 0;
}
Output:
Asha asha kiran neha Ravi
Asha and asha compare equal here, so either may come first.
3. Sort dates, oldest first. Three keys: year, then month, then day.
Solution
#include <stdio.h>
#include <stdlib.h>
struct Date {
int d, m, y;
};
int cmpdate(const void *a, const void *b) {
const struct Date *p = a, *q = b;
if (p->y != q->y) return (p->y > q->y) - (p->y < q->y);
if (p->m != q->m) return (p->m > q->m) - (p->m < q->m);
return (p->d > q->d) - (p->d < q->d);
}
int main() {
struct Date t[] = {{15, 8, 2024}, {26, 1, 2024}, {2, 10, 2023}, {14, 11, 2024}, {26, 1, 2023}};
int n = sizeof(t) / sizeof(t[0]);
qsort(t, n, sizeof(t[0]), cmpdate);
for (int i = 0; i < n; i++) printf("%02d-%02d-%d\n", t[i].d, t[i].m, t[i].y);
return 0;
}
Output:
26-01-2023
02-10-2023
26-01-2024
15-08-2024
14-11-2024
Quick quiz
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
int x = *(const int *)a, y = *(const int *)b;
return (y > x) - (y < x);
}
int main() {
int a[] = {3, 1, 2};
qsort(a, 3, sizeof(int), cmp);
printf("%d %d %d\n", a[0], a[1], a[2]);
return 0;
}
(A) 3 2 1 (B) 1 2 3 (C) 3 1 2 (D) 2 1 3
Answer
(A) 3 2 1. x and y are swapped: when x is bigger, y > x is 0 and y < x is 1, so it returns −1 and the bigger value comes first. Descending order.
Output:
3 2 1
Interview questions
- What are the four arguments of
qsort? The array, the number of elements, the size of one element, and the comparator. - What must a comparator return? Negative if the first argument comes first, zero if equal, positive if the second comes first.
- Why is
return a - b;a bad comparator? It overflows for values far apart (like 2 billion and −2 billion), which is undefined behaviour and gives a wrong order. - Why does a comparator take
const void *?qsortworks for any type, so it passes untyped read-only pointers; you cast them back. - How do you sort an array of
char *withqsort? A wrapper that doesstrcmp(*(char *const *)a, *(char *const *)b). - Is
qsortstable? The C standard doesn't promise it. Put every tie-breaker in the comparator. - How do you sort by two keys? Compare the first key; if equal, compare the second.
- Sort big structs fast? Sort an array of pointers to them, so
qsortmoves 8 bytes instead of the whole struct. - What does
qsortguarantee about speed? The C standard says nothing; glibc's is O(n log n). Bubble, selection and insertion sort are O(n²).
Glossary
| Term | Meaning | Example |
|---|---|---|
qsort |
The C library's general sort, in <stdlib.h> |
qsort(a, n, sizeof(a[0]), cmp) |
| Comparator | A function that says which of two elements comes first | returns −1, 0 or 1 |
void * |
A pointer to any type | what qsort passes |
const void * |
A read-only pointer to any type | int cmp(const void *a, const void *b) |
| Cast | Converting a value to another type | (const int *)a |
| Dereference | Reading what a pointer points at, with * |
*(const int *)a |
size_t |
The unsigned type of sizes, from sizeof |
sizeof(int) is 4 |
INT_MAX / INT_MIN |
The largest / smallest int |
2,147,483,647 / −2,147,483,648 |
| Signed overflow | A signed result too big for its type: undefined behaviour | 2e9 - (-2e9) in int |
| Undefined behaviour (UB) | The C standard makes no promise | a wrong order here |
strcmp |
Compares two strings by character codes | strcmp("Asha", "Ravi") < 0 |
| Character code (ASCII) | The number stored for a character | 'A' = 65, 'a' = 97 |
| Array of pointers | An array whose elements are addresses | char *name[100] |
char ** |
A pointer to a char * |
&name[i] |
-Wincompatible-pointer-types |
gcc's warning for a pointer of the wrong type | strcmp given to qsort |
struct |
A type grouping related fields | struct Student { char name[21]; int marks; } |
Arrow -> |
Reads a field through a pointer | p->marks is (*p).marks |
| Key | The value you sort by | marks |
| Tie-breaker (second key) | The value used when the first keys are equal | the name |
| Stable sort | Keeps equal elements in their input order | not promised for qsort |
| Consistent comparator | Always gives the same answer for the same pair | required by qsort |
| Bubble sort | Swapping wrong-order neighbours, pass after pass | O(n²) |
| O(n log n) | About n × log₂ n steps | 200,000 → about 3.5 million |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | 8 seconds here |
tolower |
Turns a capital letter into a small one | tolower('A') is 'a' |
Summary
qsort(a, n, sizeof(a[0]), cmp)sorts any array in about O(n log n); bubble sort's O(n²) times out on 200,000 numbers.- A comparator returns negative, zero or positive. Never
a - b(it overflows); use(x > y) - (x < y). - For an array of
char *, the comparator gets achar **: dereference once, thenstrcmp. Passingstrcmpstraight in is a warning and a wrong order. - Two keys: compare the first; on a tie, the second.
qsortis not stable, so the tie-breaker must be in the comparator.
Next episode: String questions I: string length without strlen, reversing a string in place, and a palindrome string (ignoring case and spaces).