algorithms-data-structures

# Algorithms & Data Structures

An algorithm is a finite, unambiguous sequence of well-defined instructions for solving a class of problems. A data structure is an organization of data that enables efficient access and modification. Together they form the mechanical foundation of all computation. This skill catalogs the canonical algorithms and data structures with complexity analysis, implementation notes, and selection heuristics.

**Agent affinity:** knuth (algorithm analysis, literate implementation), turing (computability, theoretical limits)

**Concept IDs:** code-sorting-algorithms, code-searching-algorithms, code-big-o-notation, code-dynamic-programming

## Complexity Analysis at a Glance

Before studying individual algorithms, internalize the complexity hierarchy. Every algorithm has a time cost and a space cost, each expressed as a function of input size n.

| Class | Name | Example |
|---|---|---|
| O(1) | Constant | Array index access, hash table lookup (average) |
| O(log n) | Logarithmic | Binary search, balanced BST lookup |
| O(n) | Linear | Linear search, single traversal |
| O(n log n) | Linearithmic | Merge sort, heap sort, efficient comparison sorts |
| O(n^2) | Quadratic | Bubble sort, insertion sort (worst), naive string matching |
| O(n^3) | Cubic | Naive matrix multiplication, Floyd-Warshall |
| O(2^n) | Exponential | Brute-force subset enumeration, naive recursive Fibonacci |
| O(n!) | Factorial | Brute-force permutation, naive TSP |

**Big-O** gives the asymptotic upper bound. **Big-Omega** gives the lower bound. **Big-Theta** gives the tight bound (both upper and lower). When we say "merge sort is O(n log n)," we mean its worst-case running time grows no faster than c * n * log(n) for some constant c and sufficiently large n. More precisely, merge sort is Theta(n log n) because its best, average, and worst cases all share this growth rate.

**Amortized analysis** applies when individual operations vary in cost but the average over a sequence is predictable. The classic example is dynamic array resizing: a single push may cost O(n) when the array doubles, but amortized over n pushes, each costs O(1).

## Part 1 -- Sorting Algorithms

Sorting is the most studied problem in computer science. Comparison-based sorting has a proven lower bound of Omega(n log n) -- no comparison sort can do better in the worst case. Non-comparison sorts (radix, counting, bucket) can beat this bound when the data admits it.

### 1.1 -- Bubble Sort

**Mechanism:** Repeatedly walk the array, swapping adjacent elements that are out of order. After pass k, the k-th largest element is in its final position.

**Complexity:** O(n^2) time worst/average, O(n) best (already sorted, with early-exit optimization). O(1) space. Stable.

**When to use:** Almost never in production. Its value is pedagogical -- it is the simplest sorting algorithm to understand and proves that sorting is achievable through local comparisons alone.

**The early-exit optimization.** If a full pass completes with zero swaps, the array is sorted. This gives O(n) best case, making bubble sort adaptive -- it benefits from pre-existing order.

### 1.2 -- Insertion Sort

**Mechanism:** Build the sorted portion one element at a time. For each new element, shift larger elements right and insert into the correct position.

**Complexity:** O(n^2) worst/average, O(n) best (nearly sorted). O(1) space. Stable. Adaptive.

**When to use:** Small arrays (n < 20-50), nearly sorted data, online sorting (elements arrive one at a time). Many optimized sort implementations (including Timsort) use insertion sort for small partitions.

**Why it beats bubble sort.** Insertion sort performs at most n-1 comparisons on sorted input and does fewer swaps on average because it moves elements directly to their correct position rather than bubbling them one step at a time.

### 1.3 -- Selection Sort

**Mechanism:** Find the minimum element in the unsorted portion and swap it to the front. Repeat.

**Complexity:** O(n^2) in all cases. O(1) space. Not stable (swaps can break equal-element ordering). Not adaptive.

**When to use:** When write operations are expensive (flash memory, EEPROM) -- selection sort performs exactly n-1 swaps regardless of input. This is its only practical advantage.

### 1.4 -- Merge Sort

**Mechanism:** Divide the array in half, recursively sort each half, merge the sorted halves.

**Complexity:** Theta(n log n) in all cases. O(n) auxiliary space (for the merge buffer). Stable.

**The merge operation.** Two pointers walk the two sorted halves. At each step, the smaller element is copied to the output. This is O(n) per level, and there are log(n) levels, giving n log n total.

**When to use:** When stability is required, when worst-case guarantees matter, when data is on disk (merge sort's sequential access pattern is cache-friendly for external sorting). Java's Arrays.sort for objects uses a merge sort variant (Timsort).

**Recurrence relation:** T(n) = 2T(n/2) + O(n). By the Master Theorem (case 2), T(n) = Theta(n log n).

### 1.5 -- Quick Sort

**Mechanism:** Choose a pivot, partition the array so all elements less than the pivot come before it and all greater come after, recursively sort the partitions.

**Complexity:** O(n log n) average, O(n^2) worst (pathological pivot choices). O(log n) space (recursion stack, in-place). Not stable (Lomuto/Hoare partition swaps non-adjacent elements).

**Pivot selection strategies.** Random pivot gives O(n log n) expected time. Median-of-three (first, middle, last) avoids worst case on sorted input. Introselect (switch to heap sort after recursion depth exceeds 2 log n) guarantees O(n log n) worst case -- this is introsort, used by C++ std::sort.

**When to use:** Default choice for in-memory sorting when stability is not required. Cache performance is excellent (sequential access within partitions). In practice, quicksort with good pivot selection beats merge sort due to lower constant f