SyntaxPilot
Courses/C Coding Questions/Lesson 14
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 14 of 30

Sorting questions II

qsort with a comparator (the subtraction overflow bug)sort an array of stringssort structs by two keys

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). qsort does 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 a should come first, 0 if they are equal, a positive number if b should 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 then return 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

  1. What are the four arguments of qsort? The array, the number of elements, the size of one element, and the comparator.
  2. What must a comparator return? Negative if the first argument comes first, zero if equal, positive if the second comes first.
  3. 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.
  4. Why does a comparator take const void *? qsort works for any type, so it passes untyped read-only pointers; you cast them back.
  5. How do you sort an array of char * with qsort? A wrapper that does strcmp(*(char *const *)a, *(char *const *)b).
  6. Is qsort stable? The C standard doesn't promise it. Put every tie-breaker in the comparator.
  7. How do you sort by two keys? Compare the first key; if equal, compare the second.
  8. Sort big structs fast? Sort an array of pointers to them, so qsort moves 8 bytes instead of the whole struct.
  9. What does qsort guarantee 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 a char **: dereference once, then strcmp. Passing strcmp straight in is a warning and a wrong order.
  • Two keys: compare the first; on a tie, the second. qsort is 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).