C · Advanced

Sorting and Searching in C

In short: Sorting arranges an array in order; searching finds where a value sits. A linear search checks each element and needs no order, while binary search on a sorted array halves the range at every step. The C library provides qsort and bsearch, which take a comparison function you write that returns a negative, zero or positive int.

Why sort, and how to search

Finding a value in an unsorted array means checking elements one by one until it turns up: a linear search. For a few dozen values that is fine, and it is the right tool when the data is unordered or searched only once. When the same array is searched many times, sorting it first pays for itself, because a sorted array can be searched by halving: look at the middle element, decide which half must contain the target, and repeat. That binary search reaches any of a million elements in about twenty comparisons rather than up to a million.

Sorting can be written by hand. Insertion sort takes each element in turn and slides it left past every larger neighbour until it sits in order among the elements already processed, the way a hand of cards is tidied. It is short, easy to get right and quick for small or nearly sorted arrays, but the number of moves grows with the square of the length, so ten times the data means about a hundred times the work.

For anything larger, use the library's qsort, declared in <stdlib.h>: qsort(array, count, sizeof array[0], compare). It works on any element type because it never looks inside the elements itself; it calls your compare function with pointers to two of them, declared as const void *, and expects a negative, zero or positive result meaning the first should come before, level with, or after the second. Inside the function you convert the pointers to the real type and compare the members you choose. Sorting an array of structs by one field and then by another is just two comparison functions. Avoid return a - b for ints, because the subtraction can overflow; (a > b) - (a < b) gives the sign safely.

bsearch(&key, array, count, size, compare) from the same header performs a binary search with the same kind of comparison function and returns a pointer to a matching element or NULL. It requires the array to be sorted by that comparison; on unsorted data it returns nonsense without warning. Writing binary search yourself is worth doing once to see the mechanics: two indexes bracket the candidate range, the middle is examined, and one bound moves past it. The two classic bugs are computing the middle as (lo + hi) / 2, which can overflow for huge arrays, and moving a bound to mid instead of past it, which can loop forever.

qsort is not guaranteed to be stable: elements that compare equal may come out in any order. When the original order of ties matters, add a tie-break to the comparison, such as an original index stored in the struct.

Syntax

#include <stdlib.h>

int compare_int(const void *a, const void *b) {
    int x = *(const int *) a;
    int y = *(const int *) b;
    return (x > y) - (x < y);        /* -1, 0 or 1, and cannot overflow */
}

qsort(values, n, sizeof values[0], compare_int);          /* sorts in place */

int key = 42;
int *hit = bsearch(&key, values, n, sizeof values[0], compare_int);
if (hit != NULL) {
    int index = hit - values;        /* pointer to index */
}

/* comparing structs by a member */
int by_name(const void *a, const void *b) {
    const struct Runner *x = a;
    const struct Runner *y = b;
    return strcmp(x->name, y->name);
}

The comparison function receives pointers to elements, never the elements themselves. To sort in descending order, swap the roles of x and y in the return expression.

How the cost grows

Insertion sort and linear search by hand

Six crate weights, searched before and after sorting.

#include <stdio.h>

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

int linear_search(const int a[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (a[i] == target) {
            return i;
        }
    }
    return -1;
}

void print_array(const int a[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d%c", a[i], i + 1 < n ? ' ' : '\n');
    }
}

int main(void) {
    int crates[6] = {48, 12, 27, 35, 12, 9};

    printf("27 found at index %d\n", linear_search(crates, 6, 27));
    insertion_sort(crates, 6);
    print_array(crates, 6);
    printf("27 found at index %d\n", linear_search(crates, 6, 27));
    printf("30 found at index %d\n", linear_search(crates, 6, 30));
    return 0;
}

27 found at index 2
9 12 12 27 35 48
27 found at index 3
30 found at index -1

The first search finds 27 at index 2 by scanning from the left. insertion_sort then takes each element from index 1 onwards, shifts larger elements one place to the right, and drops the element into the gap, so after the loop the array reads 9 12 12 27 35 48 and 27 has moved to index 3. The duplicate 12s are kept: sorting rearranges but never discards. A search for 30 returns -1, the conventional not-found value, which the caller must check for before using the index.

qsort on ints and on structs

Lap times sorted descending, then runners sorted by finishing time and again by name.

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

struct Runner {
    char name[12];
    int seconds;
};

int by_seconds(const void *a, const void *b) {
    const struct Runner *x = a;
    const struct Runner *y = b;
    return (x->seconds > y->seconds) - (x->seconds < y->seconds);
}

int by_name(const void *a, const void *b) {
    const struct Runner *x = a;
    const struct Runner *y = b;
    return strcmp(x->name, y->name);
}

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

int main(void) {
    int laps[5] = {71, 68, 75, 64, 70};
    qsort(laps, 5, sizeof laps[0], descending_int);
    for (int i = 0; i < 5; i++) {
        printf("%d%c", laps[i], i < 4 ? ' ' : '\n');
    }

    struct Runner field[4] = {
        { "Priya", 1502 }, { "Tomasz", 1388 }, { "Ines", 1450 }, { "Kofi", 1421 }
    };
    qsort(field, 4, sizeof field[0], by_seconds);
    for (int i = 0; i < 4; i++) {
        printf("%s %d:%02d\n", field[i].name, field[i].seconds / 60, field[i].seconds % 60);
    }

    qsort(field, 4, sizeof field[0], by_name);
    for (int i = 0; i < 4; i++) {
        printf("%s%c", field[i].name, i < 3 ? ' ' : '\n');
    }
    return 0;
}

75 71 70 68 64
Tomasz 23:08
Kofi 23:41
Ines 24:10
Priya 25:02
Ines Kofi Priya Tomasz

descending_int compares y against x, which reverses the order. The runner comparisons convert the const void * arguments back to const struct Runner * and compare one member: by_seconds uses the overflow-safe idiom and by_name delegates to strcmp, which already returns a suitably signed int. The same array is sorted twice by two different criteria without any change to the data, which is the point of passing the comparison as a function. Note the element size argument: sizeof field[0] is the size of one struct, and getting it wrong is the most common qsort bug.

Binary search, traced step by step

Ten sorted shelf codes, a value that is present and one that is not, then bsearch for comparison.

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

int binary_search(const int a[], int n, int target) {
    int lo = 0, hi = n - 1;
    int step = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        step++;
        printf("  step %d: index %d holds %d\n", step, mid, a[mid]);
        if (a[mid] == target) {
            return mid;
        }
        if (a[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}

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

int main(void) {
    int shelf[10] = {103, 118, 127, 140, 156, 171, 189, 204, 220, 235};

    printf("searching for 189\n");
    printf("result: %d\n", binary_search(shelf, 10, 189));
    printf("searching for 150\n");
    printf("result: %d\n", binary_search(shelf, 10, 150));

    int key = 220;
    int *hit = bsearch(&key, shelf, 10, sizeof shelf[0], compare_int);
    if (hit != NULL) {
        printf("bsearch: %d is at index %d\n", key, (int) (hit - shelf));
    }
    return 0;
}

searching for 189
  step 1: index 4 holds 156
  step 2: index 7 holds 204
  step 3: index 5 holds 171
  step 4: index 6 holds 189
result: 6
searching for 150
  step 1: index 4 holds 156
  step 2: index 1 holds 118
  step 3: index 2 holds 127
  step 4: index 3 holds 140
result: -1
bsearch: 220 is at index 8

Each step prints the index it examines. For 189 the range narrows from ten elements to five, to two, to one, and the fourth probe hits. For 150, which is absent, the bounds cross after four probes: lo becomes 4 while hi is 3, the loop condition fails and the function returns -1. Four probes for ten elements matches the log2 estimate. bsearch does the same work through the comparison function and returns a pointer; subtracting the array's start converts it to an index, and a NULL result would mean the key is absent.

Common mistakes

• Returning a - b from the comparison function

  Why it goes wrong: For large ints the subtraction overflows: comparing 2000000000 with -2000000000 gives a negative result, so the larger value sorts first and the order is wrong.

  Fix: Return (x > y) - (x < y), which is always -1, 0 or 1.

   C · fixCopy

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

• Calling bsearch or binary search on unsorted data

  Why it goes wrong: Binary search decides which half to discard by assuming order. On unsorted data it discards halves that may contain the target and reports it missing, or finds only one of several matches.

  Fix: Sort first with qsort using the same comparison function, or use a linear search if the data cannot be sorted.

• Passing the wrong element size to qsort

  Why it goes wrong: qsort(field, 4, sizeof field, by_name) or sizeof(struct Runner *) makes qsort step through memory with the wrong stride, mixing bytes of neighbouring elements.

  Fix: Always pass sizeof array[0], the size of one element.

• Moving a bound to mid instead of past it

  Why it goes wrong: hi = mid when a[mid] > target can leave lo and hi unchanged when they are one apart, and the loop never ends.

  Fix: After examining mid, exclude it: lo = mid + 1 or hi = mid - 1.

Where you use this

A results program reads race entries into an array of structs, sorts them by time with qsort to print the standings, then sorts by name to print an alphabetical list, with no change to the reading code. Sorting is also the first step of other tasks: after sorting, duplicates sit next to each other and can be removed in one pass, the median is the middle element, and repeated lookups by code can use bsearch instead of scanning. When records come from a file, the file handling lesson covers reading them in; when their number is unknown, the array comes from malloc.

qsort(entries, n, sizeof entries[0], by_name);   /* equal names are now adjacent */
int unique = 0;
for (int i = 0; i < n; i++) {
    if (unique == 0 || strcmp(entries[i].name, entries[unique - 1].name) != 0) {
        entries[unique++] = entries[i];
    }
}
/* entries[0 .. unique) now holds one record per name */

Key points

• Linear search works on any array; binary search needs a sorted one and takes about log2(n) steps.
• qsort(array, n, sizeof array[0], compare) sorts any element type in place.
• A comparison function receives const void * pointers and returns negative, zero or positive.
• Use (x > y) - (x < y) for numbers and strcmp for strings; avoid subtraction.
• bsearch returns a pointer to a match or NULL, and only works on data sorted by the same comparison.
• qsort is not stable; add a tie-break when the order of equal elements matters.

Try it yourself

Complete the comparison function and the rest of main: sort the values in ascending order with qsort, print them on one line separated by spaces, then print median followed by the middle element (index n / 2). For the input 5 and 31 7 19 22 4 the output is 4 7 19 22 31 and median 19.

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

int ascending(const void *a, const void *b) {
    return 0;   /* replace: negative if *a < *b, zero if equal, positive if greater */
}

int main(void) {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0 || n > 100) {
        return 1;
    }
    int values[100];
    for (int i = 0; i < n; i++) {
        if (scanf("%d", &values[i]) != 1) {
            return 1;
        }
    }

    /* sort values with qsort, print them on one line, then print "median <middle value>" */

    return 0;
}

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

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

int main(void) {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0 || n > 100) {
        return 1;
    }
    int values[100];
    for (int i = 0; i < n; i++) {
        if (scanf("%d", &values[i]) != 1) {
            return 1;
        }
    }

    qsort(values, n, sizeof values[0], ascending);
    for (int i = 0; i < n; i++) {
        printf("%d%c", values[i], i < n - 1 ? ' ' : '\n');
    }
    printf("median %d\n", values[n / 2]);
    return 0;
}

Practise this

Exercises for this lesson are in the C practice set.

Open the C playground

Related lessons

• Arrays in CHow C arrays store same-typed values by zero-based index: initialiser lists, the sizeof length idiom, passing arrays to functions and out-of-range dangers.10 minCompleted
• Structures in CHow a C struct bundles related values into one record, how to initialise, copy and pass structs to functions, and when to use -> instead of the dot.9 minCompleted
• Functions in CHow to define and call C functions: prototypes before the first call, arguments copied by value, void functions, early returns and local variables.10 minCompleted
• Recursion in CHow recursive functions work in C: base and recursive cases, what happens on the call stack, digit and array recursion, and merge sort as divide and conquer.10 minCompleted

Frequently asked questions

How this page was checked. Every program on it was run with GCC 13 (C11) at build time by the publishing checks, and the output shown is what it printed. Running C inside the browser is not available yet, so the Run button is absent rather than pretending; copy the code and run it with GCC 13 (C11) locally.