Loading...

C essentialsData Structures

Sorting & searching algorithms

18 min lesson

Next
  • Sorting arranges data in order, and searching finds an item; together they are the most common operations on collections.
  • They matter because sorted data enables fast search, and choosing the right algorithm changes performance dramatically on large inputs.
  • Think of sorting as arranging a deck of cards in your hand, and searching as finding a specific card: linear search flips through one by one, binary search splits the deck in half.
  • Bubble sort repeatedly swaps adjacent out-of-order items; it is easy to understand but slow (O(n^2)) for large data.
  • Insertion sort builds a sorted section one item at a time; it is also O(n^2) but fast on small or nearly sorted arrays.
  • Binary search works only on sorted data and repeatedly halves the range, giving O(log n) comparisons.
  • The computer compares values and moves items in memory; faster algorithms do fewer comparisons and moves.
  • The syntax for binary search is: lo = 0, hi = n - 1; while (lo <= hi) { mid = (lo + hi) / 2; ... }.
  • A realistic use: sorting a list of names and then searching for one name quickly, or sorting prices before finding a range.
  • A surprising detail: binary search is fast but only correct on sorted data; a single unsorted item breaks it silently.
  • The example program sorts an array with insertion sort, prints it, then searches for a value with binary search.
Keep in mind
  • Sort first, then use binary search for fast lookup.
  • Use insertion sort for small or nearly sorted arrays; it is simple and fast enough.
  • Remember binary search requires sorted data; otherwise results are wrong.
  • Measure with real data; O(n^2) is fine for hundreds but slow for millions.
  • These algorithms are the foundation of computer science. You did great!
main.c
#include <stdio.h>

// Insertion sort: build a sorted section one item at a time
void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        // Save the value we are placing
        int key = a[i];
        int j = i - 1;
        // Shift larger values to the right to make room
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        // Place the value in its sorted position
        a[j + 1] = key;
    }
}

// Binary search on sorted data; returns index or -1
int binarySearch(const int a[], int n, int target) {
    int lo = 0;
    int hi = n - 1;
    while (lo <= hi) {
        // Midpoint, safe from overflow for reasonable sizes
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main(void) {
    // An unsorted array of values
    int a[] = {42, 7, 19, 3, 88, 25};
    int n = (int)(sizeof a / sizeof a[0]);

    // Sort the array in place
    insertionSort(a, n);

    // Print the sorted array
    printf("Sorted: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    // Search for two targets
    printf("Index of 25: %d\n", binarySearch(a, n, 25));
    printf("Index of 99: %d\n", binarySearch(a, n, 99));
    return 0;
}

What happens: Sorted: 3 7 19 25 42 88 Index of 25: 3 Index of 99: -1

Breaking it down

Insertion sort outer loop

for (int i = 1; i < n; i++)

Starts from the second element; the first element is a sorted section of size 1.

Shifting

while (j >= 0 && a[j] > key) a[j + 1] = a[j];

Moves larger values one slot to the right to make room for the key. This keeps the sorted section in order.

Placing the key

a[j + 1] = key;

Puts the saved value into the gap. After each pass, one more element is sorted.

Binary search midpoint

int mid = lo + (hi - lo) / 2;

Splits the range in half. This form avoids overflow that (lo + hi) / 2 can cause on large arrays.

Binary search step

if (a[mid] < target) lo = mid + 1;

Discards the half that cannot contain the target. Each step halves the range, giving O(log n).

Common algorithms

AlgorithmBest useAverage time
Bubble sortTeaching onlyO(n^2)
Insertion sortSmall or nearly sortedO(n^2)
QuicksortGeneral purposeO(n log n)
Merge sortStable, predictableO(n log n)
Linear searchUnsorted dataO(n)
Binary searchSorted dataO(log n)

A helpful analogy

Sorting is like arranging a deck of cards in your hand: you pick a card and slide it into the right spot. Searching is like finding a specific card: linear search flips through one by one, while binary search splits the sorted deck in half again and again.

Nesting rules

  • 1.Binary search only works on sorted data; sort first if needed.
  • 2.Use mid = lo + (hi - lo) / 2 to avoid overflow in the midpoint calculation.
  • 3.The binary search loop continues while lo <= hi, and ends with -1 when not found.
  • 4.Insertion sort is stable and in-place; it is a good choice for small arrays.

Common mistakes

Running binary search on unsorted data

Avoid

binarySearch on {3, 1, 2} // wrong results

Use instead

sort first, then binarySearch

Binary search relies on sorted order to discard half the range. On unsorted data it silently returns wrong answers.

Overflow in the midpoint

Avoid

int mid = (lo + hi) / 2; // overflow

Use instead

int mid = lo + (hi - lo) / 2;

If lo and hi are both large, lo + hi can overflow. The safe form avoids that.

Using <= in the insertion sort shift

Avoid

while (j >= 0 && a[j] >= key)

Use instead

while (j >= 0 && a[j] > key)

Using >= moves equal values and breaks stability. Use > to keep equal elements in their original order.

Quick tips

  • •Trace insertion sort on a small array like {3, 1, 2} by hand to see the shifts.
  • •Print the array after each pass to watch it become sorted.
  • •Learn one fast sort like quicksort or merge sort after mastering these basics.
  • •Try changing the target to 42 in the example to see a different index.
  • •Use qsort from stdlib.h in real code; it is fast and well tested.
Previous
Next