Searching and Sorting Arrays in C

Searching and sorting are the first algorithms every programmer learns, and they're asked in almost every C lab exam and campus test. Writing them yourself shows you how to reason about loops, swaps and efficiency; in real programs you'll then use the standard library's qsort.

Linear search

#include <stdio.h>

int linear_search(const int a[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (a[i] == key) return i;     // found: return its index
    }
    return -1;                         // not found
}

int main(void) {
    int roll_numbers[] = {104, 87, 23, 56, 91, 12};
    int n = sizeof roll_numbers / sizeof roll_numbers[0];
    printf("56 found at index %d\n", linear_search(roll_numbers, n, 56));
    printf("99 found at index %d\n", linear_search(roll_numbers, n, 99));
    return 0;
}

56 found at index 3
99 found at index -1

Linear search checks every element – up to n comparisons. It works on any array, sorted or not.

Binary search (sorted arrays)

#include <stdio.h>

int binary_search(const int a[], int n, int key) {
    int low = 0, high = n - 1, steps = 0;
    while (low <= high) {
        steps++;
        int mid = low + (high - low) / 2;     // avoids overflow of (low + high)
        if (a[mid] == key) { printf("  (%d steps) ", steps); return mid; }
        if (a[mid] < key) low = mid + 1;      // key is in the right half
        else high = mid - 1;                  // key is in the left half
    }
    printf("  (%d steps) ", steps);
    return -1;
}

int main(void) {
    int a[] = {3, 8, 15, 23, 42, 56, 71, 89, 94, 99};
    int n = sizeof a / sizeof a[0];
    printf("index %d\n", binary_search(a, n, 71));
    printf("index %d\n", binary_search(a, n, 4));
    return 0;
}

  (4 steps) index 6
  (3 steps) index -1

A million sorted items need at most about 20 steps (log₂ 1,000,000 ≈ 20), versus up to a million for linear search. The array must be sorted.

Three simple sorts

#include <stdio.h>
#include <stdbool.h>

void print(const char *label, const int a[], int n) {
    printf("%-10s", label);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
}

void bubble_sort(int a[], int n) {            // swap neighbours; big values "bubble" to the end
    for (int pass = 0; pass < n - 1; pass++) {
        bool swapped = false;
        for (int i = 0; i < n - 1 - pass; i++) {
            if (a[i] > a[i + 1]) {
                int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;
                swapped = true;
            }
        }
        if (!swapped) break;                  // already sorted: stop early
    }
}

void selection_sort(int a[], int n) {         // pick the smallest remaining, put it next
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) if (a[j] < a[min]) min = j;
        int t = a[i]; a[i] = a[min]; a[min] = t;
    }
}

void insertion_sort(int a[], int n) {         // insert each value into the sorted left part
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

int main(void) {
    int x[] = {64, 25, 12, 22, 11}, y[] = {64, 25, 12, 22, 11}, z[] = {64, 25, 12, 22, 11};
    bubble_sort(x, 5);    print("bubble:", x, 5);
    selection_sort(y, 5); print("selection:", y, 5);
    insertion_sort(z, 5); print("insertion:", z, 5);
    return 0;
}

bubble:   11 12 22 25 64 
selection:11 12 22 25 64 
insertion:11 12 22 25 64 

O(n²) means the work grows with the square of the size: double the data, four times the work. That's fine for 100 items and hopeless for a million – which is why real programs use O(n log n) sorts.

qsort: the standard library sort

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

int ascending(const void *a, const void *b) {
    int x = *(const int *)a, y = *(const int *)b;
    return (x > y) - (x < y);                // negative, zero or positive (no overflow)
}

int descending(const void *a, const void *b) {
    return ascending(b, a);
}

int main(void) {
    int scores[] = {72, 95, 41, 88, 60, 95};
    int n = sizeof scores / sizeof scores[0];
    qsort(scores, n, sizeof scores[0], ascending);
    for (int i = 0; i < n; i++) printf("%d ", scores[i]);
    printf("\n");
    qsort(scores, n, sizeof scores[0], descending);
    for (int i = 0; i < n; i++) printf("%d ", scores[i]);
    printf("\n");
    return 0;
}

41 60 72 88 95 95 
95 95 88 72 60 41 

qsort sorts any type: you pass the array, the count, the size of one element and a comparison function. The comparator receives void pointers that you cast to the real type – you'll understand this fully after the pointers chapter. Chapter 10 uses it to sort structures.

Practice

Summary

Interview practice: arrays and functions interview questions.