Sorting and Searching

Sorting data and finding things in it are among the most common jobs a program does. C's standard library provides a general-purpose sort, qsort, and binary search, bsearch, that work on arrays of any type — once you know how to write the comparison function.

Sorting numbers with qsort

qsort(base, count, size, compare) sorts an array in place. You supply a function that receives pointers to two elements and returns a negative number, zero or a positive number:

C 
#include <stdio.h>
#include <stdlib.h>

int compare_doubles(const void *a, const void *b) {
    double x = *(const double *) a;
    double y = *(const double *) b;
    return (x > y) - (x < y);
}

int main(void) {
    double times[] = { 12.4, 9.81, 11.02, 9.58, 10.0 };
    size_t n = sizeof times / sizeof times[0];
    qsort(times, n, sizeof times[0], compare_doubles);
    for (size_t i = 0; i < n; i++) printf("%.2f ", times[i]);
    printf("\n");
    return 0;
}
Output
9.58 9.81 10.00 11.02 12.40

Sorting structs

The comparison can look at any member, and break ties with a second one:

C 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char name[16];
    int points;
} Team;

int by_points_then_name(const void *a, const void *b) {
    const Team *x = a, *y = b;
    if (x->points != y->points) return y->points - x->points;   // more points first
    return strcmp(x->name, y->name);                            // then alphabetical
}

int main(void) {
    Team table[] = { { "Rovers", 54 }, { "Athletic", 61 }, { "City", 54 }, { "United", 47 } };
    size_t n = sizeof table / sizeof table[0];
    qsort(table, n, sizeof table[0], by_points_then_name);
    for (size_t i = 0; i < n; i++) {
        printf("%zu. %-10s %d\n", i + 1, table[i].name, table[i].points);
    }
    return 0;
}
Output
1. Athletic   61
2. City       54
3. Rovers     54
4. United     47

const Team *x = a; converts the const void * back to the real type — no cast is needed in C.

Sorting strings

For an array of char *, each element is a pointer, so the comparison receives pointers to pointers:

C 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare_strings(const void *a, const void *b) {
    const char *const *x = a;
    const char *const *y = b;
    return strcmp(*x, *y);
}

int main(void) {
    const char *fruits[] = { "pear", "apple", "fig", "banana", "cherry" };
    size_t n = sizeof fruits / sizeof fruits[0];
    qsort(fruits, n, sizeof fruits[0], compare_strings);
    for (size_t i = 0; i < n; i++) printf("%s ", fruits[i]);
    printf("\n");
    return 0;
}
Output
apple banana cherry fig pear

Passing strcmp directly would be a bug: it would receive pointers to the pointers, not the strings.

Binary search with bsearch

On a sorted array, bsearch finds an element in about log2(n) steps. It returns a pointer to the match, or NULL, and uses the same kind of comparison function:

C 
#include <stdio.h>
#include <stdlib.h>

int compare_ints(const void *a, const void *b) {
    int x = *(const int *) a, y = *(const int *) b;
    return (x > y) - (x < y);
}

int main(void) {
    int ids[] = { 1043, 1187, 1201, 1356, 1499, 1602, 1777 };
    size_t n = sizeof ids / sizeof ids[0];
    int wanted[] = { 1356, 1400 };
    for (int i = 0; i < 2; i++) {
        int *found = bsearch(&wanted[i], ids, n, sizeof ids[0], compare_ints);
        if (found) printf("%d found at index %td\n", wanted[i], found - ids);
        else printf("%d not found\n", wanted[i]);
    }
    return 0;
}
Output
1356 found at index 3
1400 not found

Writing a sort yourself

Insertion sort is simple and fast for small or nearly sorted arrays — which is why real sort implementations often switch to it for short ranges:

C 
#include <stdio.h>

void insertion_sort(int *a, size_t n) {
    for (size_t i = 1; i < n; i++) {
        int key = a[i];
        size_t j = i;
        while (j > 0 && a[j - 1] > key) {
            a[j] = a[j - 1];    // shift larger elements right
            j--;
        }
        a[j] = key;
    }
}

int main(void) {
    int cards[] = { 7, 2, 9, 4, 1, 8 };
    insertion_sort(cards, 6);
    for (int i = 0; i < 6; i++) printf("%d ", cards[i]);
    printf("\n");
    return 0;
}
Output
1 2 4 7 8 9

Insertion sort takes time proportional to n² in the worst case; qsort implementations use O(n log n) algorithms. For large data, use the library.

Comparison function rules

  • Return negative, zero or positive — only the sign matters.
  • Be consistent: if a < b and b < c, then a < c must hold, or the sort may misbehave.
  • Avoid return x - y; for values that might overflow (large or mixed-sign integers).
  • qsort isn't stable: equal elements may end up in any order. Add a tie-breaker if order matters.

Try it yourself

Sort words by length (shortest first), with alphabetical order for words of equal length.

Try it yourself · main.c
Edit the code, copy it into main.c, then compile and run it with cc -std=c17 -Wall main.c -o main && ./main. How to set up a C compiler
Output
fig kiwi plum apple banana cherry
PreviousLinked Lists