Sorting & searching algorithms
18 min lesson
- 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.
- 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!
#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
| Algorithm | Best use | Average time |
|---|---|---|
| Bubble sort | Teaching only | O(n^2) |
| Insertion sort | Small or nearly sorted | O(n^2) |
| Quicksort | General purpose | O(n log n) |
| Merge sort | Stable, predictable | O(n log n) |
| Linear search | Unsorted data | O(n) |
| Binary search | Sorted data | O(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 resultsUse instead
sort first, then binarySearchBinary 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; // overflowUse 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.