The tenth C++ module of the 42 curriculum, focused on STL containers and algorithms.
This project applies STL containers and algorithms to solve concrete problems, with an emphasis on choosing the right container for each use case and understanding algorithmic complexity.
Each exercise (ex00 to ex02) contains its own Makefile. Compile and run individually:
cd ex00
make
./ex00Reads a CSV price database and evaluates BTC values on given dates using std::map for efficient date lookups. The map keeps dates sorted, allowing fast nearest-date lookups with lower_bound.
A Reverse Polish Notation calculator that evaluates expressions from the command line using a std::stack. Each token is either pushed onto the stack (number) or triggers a pop of two operands and a push of the result (operator).
Sorts a sequence of positive integers using the Ford-Johnson merge-insert sort algorithm, benchmarked on both std::vector and std::deque.
Ford-Johnson (also called merge-insert sort) is a comparison sort designed to minimize the number of comparisons needed to sort n elements. It is one of the most comparison-efficient sorting algorithms known.
Step 1 — Pair and find winners
Elements are grouped into pairs and compared. The larger of each pair is the winner, the smaller is the loser. If the sequence has an odd number of elements, the last one is set aside as the straggler.
seq = [9, 1, 4, 8, 6, 3, 7] straggler = 7
pairs = [(1,9), (4,8), (3,6)]
winners = [9, 8, 6]
Step 2 — Recurse on winners
The winners are sorted recursively by the same algorithm. This is the key insight: we only recurse on half the elements.
mergeInsert([9, 8, 6]) → [6, 8, 9]
Step 3 — Build the sorted chain
Once the winners are sorted, the pairs are reordered to match. The loser of the smallest winner (b1) is guaranteed to be less than everything else, so it is inserted at the front for free (0 comparisons).
sortedPairs = [(3,6), (4,8), (1,9)]
chain = [3, 6, 8, 9] ← b1=3 inserted for free
Step 4 — Insert remaining losers with binary search
The remaining losers (pending = [4, 1]) are inserted into the chain using std::lower_bound. Each binary search is bounded by the loser's paired winner — since loser ≤ winner by construction, the loser is guaranteed to be somewhere before its winner in the chain.
insert 4 (bound = 8) → [3, 4, 6, 8, 9]
insert 1 (bound = 9) → [1, 3, 4, 6, 8, 9]
Step 5 — Insert the straggler
The straggler is inserted last with a full binary search over the entire chain.
insert 7 → [1, 3, 4, 6, 7, 8, 9]
The order in which losers are inserted matters. Inserting them naively (in index order b2, b3, b4, ...) means each insertion can grow the binary search range of the next one by +1, accumulating extra comparisons over large inputs.
The Jacobsthal sequence — 1, 3, 5, 11, 21, 43... (formula: J(n) = J(n-1) + 2×J(n-2)) — defines thresholds that split the losers into groups. Within each group, insertion happens in reverse order.
Groups: [b1 free], [b3, b2], [b5, b4], [b11..b6], [b21..b12]...
Indices: [0], [2, 1], [4, 3], [10..5], [20..11]...
Why reverse order within a group?
When b3 is inserted before b2, b3 ends up somewhere in the chain above b2's bound (a3 > a2). So when b2 is later inserted with bound a2, the range it searches over does not include b3 — the range hasn't been inflated. With naive order, b2 would have already grown the range before b3 arrives.
The gain is theoretical and accumulates over large inputs (thousands of elements). For small sequences, the insertion order often produces the same comparison count — but Jacobsthal is never worse.
Example for n=4 pending:
Naive: [0, 1, 2, 3] → insert b2, b3, b4, b5
Jacobsthal: [0, 2, 1, 3] → insert b2, b4, b3, b5
| Phase | Cost |
|---|---|
| Pairing | n/2 comparisons |
| Recursive sort | T(n/2) |
| Insertion (total) | O(n log n) |
| Overall | O(n log n) |
Ford-Johnson is not the fastest sorting algorithm in practice (cache misses, pointer indirection) but it holds the theoretical record for fewest comparisons on many values of n.
The algorithm is identical for std::vector and std::deque. The benchmark demonstrates that std::vector is typically faster due to contiguous memory layout (better cache performance), while std::deque uses segmented memory and pays more for random access.