All Important Algorithms — Complete C++ Code
Every snippet below was compiled with g++ and tested. Sample outputs shown in green. CS213 /
CS293 final exam.
PART 1 — SORTING & SEARCHING
1.1 Bubble Sort — O(n²), best O(n) with early exit, stable
void bubbleSort(vector<int>& a) {
int n = [Link]();
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - 1 - i; j++) { // last i are already in place
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
swapped = true;
}
}
if (!swapped) break; // no swap in a full pass => sorted => O(n) best
}
}
1.2 Selection Sort — always O(n²) comparisons, only n−1 swaps, NOT stable
void selectionSort(vector<int>& a) {
int n = [Link]();
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) // find minimum of the unsorted part
if (a[j] < a[minIdx]) minIdx = j;
swap(a[i], a[minIdx]); // put it at the boundary
}
}
1.3 Insertion Sort — O(n²) worst, O(n) on nearly-sorted input, stable
void insertionSort(vector<int>& a) {
for (int i = 1; i < (int)[Link](); i++) {
int key = a[i]; // element to place
int j = i - 1;
while (j >= 0 && a[j] > key) { // shift bigger elements right
a[j + 1] = a[j];
j--;
}
a[j + 1] = key; // drop key into the gap
}
}
1.4 Merge Sort — O(n log n) ALWAYS, O(n) extra space, stable
void merge(vector<int>& a, int lo, int mid, int hi) {
vector<int> L([Link]() + lo, [Link]() + mid + 1);
vector<int> R([Link]() + mid + 1, [Link]() + hi + 1);
int i = 0, j = 0, k = lo;
while (i < (int)[Link]() && j < (int)[Link]()) {
if (L[i] <= R[j]) a[k++] = L[i++]; // <= : ties from LEFT => stable
else a[k++] = R[j++];
}
while (i < (int)[Link]()) a[k++] = L[i++]; // leftovers
while (j < (int)[Link]()) a[k++] = R[j++];
}
void mergeSort(vector<int>& a, int lo, int hi) {
if (lo >= hi) return; // 0 or 1 element
int mid = lo + (hi - lo) / 2;
mergeSort(a, lo, mid);
mergeSort(a, mid + 1, hi);
merge(a, lo, mid, hi);
}
// call: mergeSort(a, 0, [Link]() - 1);
1.5 Quick Sort (Lomuto partition) — O(n log n) average, O(n²) worst (sorted input,
last-element pivot), in-place, NOT stable
int partition(vector<int>& a, int lo, int hi) {
int pivot = a[hi]; // last element as pivot
int i = lo; // boundary of the "< pivot" zone
for (int j = lo; j < hi; j++) {
if (a[j] < pivot) {
swap(a[i], a[j]);
i++;
}
}
swap(a[i], a[hi]); // pivot lands in its FINAL place
return i;
}
void quickSort(vector<int>& a, int lo, int hi) {
if (lo >= hi) return;
int p = partition(a, lo, hi);
quickSort(a, lo, p - 1); // pivot excluded - it's done
quickSort(a, p + 1, hi);
}
// call: quickSort(a, 0, [Link]() - 1);
1.6 Binary Search — O(log n), array MUST be sorted
int binarySearch(vector<int>& a, int key) {
int lo = 0, hi = [Link]() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // overflow-safe midpoint
if (a[mid] == key) return mid;
if (key < a[mid]) hi = mid - 1;
else lo = mid + 1;
}
return -1; // not found
}
All six tested on {5, 2, 9, 1, 7, 3}:
bubble/selection/insertion/merge/quick: 1 2 3 5 7 9
bsearch 7 -> 4, 4 -> -1
PART 2 — MONOTONIC STACK
A stack that keeps its values sorted (increasing or decreasing) by popping everything that breaks the order
before pushing. Each index is pushed and popped at most once ⇒ O(n) total, even with the nested-looking
while loop.
2.1 Next Greater Element to the RIGHT — decreasing stack
vector<int> nextGreater(vector<int>& a) {
int n = [Link]();
vector<int> res(n, -1);
stack<int> st; // indices; their values are decreasing
for (int i = 0; i < n; i++) {
while (![Link]() && a[[Link]()] < a[i]) {
res[[Link]()] = a[i]; // a[i] is the answer for them
[Link]();
}
[Link](i); // i now waits for ITS next greater
}
return res; // whatever remains has no answer (-1)
}
2.2 Previous Smaller Element to the LEFT — increasing stack
vector<int> prevSmaller(vector<int>& a) {
int n = [Link]();
vector<int> res(n, -1);
stack<int> st; // indices; values strictly increasing
for (int i = 0; i < n; i++) {
while (![Link]() && a[[Link]()] >= a[i]) [Link](); // useless for future
if (![Link]()) res[i] = a[[Link]()];
[Link](i);
}
return res;
}
Tested on {4, 5, 2, 10, 8}:
nextGreater: 5 10 10 -1 -1
prevSmaller: -1 4 -1 2 2
The four variants: next greater / next smaller / previous greater / previous smaller — flip the comparison
and/or the scan direction. Applications: stock span, largest rectangle in histogram, daily temperatures.
PART 3 — LINKED LIST ESSENTIALS
3.1 Reverse (3-pointer) — O(n) time, O(1) space
struct Node {
int data;
Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* reverseList(Node* head) {
Node *prev = nullptr, *curr = head;
while (curr != nullptr) {
Node* nxt = curr->next; // save forward link
curr->next = prev; // flip the arrow
prev = curr; // advance prev
curr = nxt; // advance curr
}
return prev; // new head
}
3.2 Cycle detection (Floyd) + middle node — slow/fast pointers
bool hasCycle(Node* head) {
Node *slow = head, *fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next; // 1 step
fast = fast->next->next; // 2 steps
if (slow == fast) return true; // met inside a loop
}
return false; // fast fell off the end
}
Node* findMiddle(Node* head) { // when fast finishes, slow is at middle
Node *slow = head, *fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
list 1->2->3->4 reversed: 4 3 2 1 | mid 2 | cycle 0
PART 4 — BST: INSERT, SEARCH, DELETE, TRAVERSALS
All O(h) where h = height: O(log n) balanced, O(n) worst (sorted insertion order makes a chain).
struct TNode {
int key;
TNode *left, *right;
TNode(int k) : key(k), left(nullptr), right(nullptr) {}
};
TNode* insert(TNode* root, int key) {
if (!root) return new TNode(key);
if (key < root->key) root->left = insert(root->left, key);
else root->right = insert(root->right, key);
return root;
}
bool search(TNode* root, int key) {
if (!root) return false;
if (root->key == key) return true;
return key < root->key ? search(root->left, key)
: search(root->right, key);
}
TNode* findMin(TNode* root) { // leftmost node
while (root->left != nullptr) root = root->left;
return root;
}
TNode* deleteNode(TNode* root, int key) {
if (!root) return nullptr;
if (key < root->key) root->left = deleteNode(root->left, key);
else if (key > root->key) root->right = deleteNode(root->right, key);
else { // found it - 3 cases
if (!root->left) { TNode* t = root->right; delete root; return t; }
if (!root->right) { TNode* t = root->left; delete root; return t; }
TNode* succ = findMin(root->right); // 2 children: inorder successor
root->key = succ->key; // copy successor's key up
root->right = deleteNode(root->right, succ->key); // remove duplicate
}
return root;
}
void inorder(TNode* r) { if (!r) return; inorder(r->left);
cout << r->key << " "; inorder(r->right); }
void preorder(TNode* r) { if (!r) return; cout << r->key << " ";
preorder(r->left); preorder(r->right); }
void postorder(TNode* r){ if (!r) return; postorder(r->left);
postorder(r->right); cout << r->key << " "; }
int height(TNode* r) { if (!r) return -1;
return 1 + max(height(r->left), height(r->right)); }
Tested: insert {50,30,70,20,40,60,80}, delete 50:
search 40:1 45:0
after delete 50, inorder: 20 30 40 60 70 80 | height 2
Level order = BFS on the tree: push root into a queue, pop, print, push children (see Vol-2 Q1.8 for full code).
Inorder of a BST is always sorted — use it to verify answers.
PART 5 — GRAPH ALGORITHMS
Graph setup used by everything below:
int n; // number of vertices
vector<vector<int>> adj(n); // unweighted adjacency list
vector<vector<pair<int,int>>> wadj(n); // weighted: {neighbour, weight}
// undirected edge: adj[u].push_back(v); adj[v].push_back(u);
5.1 BFS — O(V + E); shortest paths in UNWEIGHTED graphs
vector<int> bfs(int n, vector<vector<int>>& adj, int src) {
vector<int> dist(n, -1); // -1 doubles as "not visited"
queue<int> q;
dist[src] = 0;
[Link](src);
while (![Link]()) {
int u = [Link](); [Link]();
for (int v : adj[u])
if (dist[v] == -1) { // first discovery = fewest edges
dist[v] = dist[u] + 1;
[Link](v);
}
}
return dist;
}
5.2 DFS — recursive — O(V + E)
void dfsRec(int u, vector<vector<int>>& adj, vector<bool>& vis) {
vis[u] = true;
cout << u << " ";
for (int v : adj[u])
if (!vis[v]) dfsRec(v, adj, vis);
}
5.3 DFS — iterative with explicit stack
void dfsIter(int n, vector<vector<int>>& adj, int src) {
vector<bool> vis(n, false);
stack<int> st;
[Link](src);
while (![Link]()) {
int u = [Link](); [Link]();
if (vis[u]) continue; // node can be pushed multiple times!
vis[u] = true;
cout << u << " ";
for (int i = adj[u].size() - 1; i >= 0; --i) // reverse push =>
if (!vis[adj[u][i]]) // recursion's order
[Link](adj[u][i]);
}
}
5.4 Connected components — BFS/DFS from every unvisited vertex
int countComponents(int n, vector<vector<int>>& adj) {
vector<bool> vis(n, false);
int comps = 0;
for (int s = 0; s < n; s++) {
if (vis[s]) continue;
comps++; // new component found
queue<int> q; [Link](s); vis[s] = true;
while (![Link]()) {
int u = [Link](); [Link]();
for (int v : adj[u])
if (!vis[v]) { vis[v] = true; [Link](v); }
}
}
return comps;
}
5.5 Cycle detection in an undirected graph — DFS + parent check
bool cycleDfs(int u, int parent, vector<vector<int>>& adj, vector<bool>& vis) {
vis[u] = true;
for (int v : adj[u]) {
if (!vis[v]) {
if (cycleDfs(v, u, adj, vis)) return true;
} else if (v != parent) // visited AND not where we came from
return true; // => back edge => cycle
}
return false;
}
// call: cycleDfs(0, -1, adj, vis) (loop over components if disconnected)
Tested on the 7-vertex graph of Vol-1 Q1.9:
BFS order: 0 1 3 2 4 5 6 dist: 0 1 2 1 2 2 3
DFS rec: 0 1 2 6 4 5 3
DFS iter: 0 1 2 6 4 5 3
components: 1 cycle: 1
5.6 Dijkstra — O((V+E) log V), weights must be ≥ 0 — with path reconstruction
#include <climits>
vector<int> dijkstra(int n, vector<vector<pair<int,int>>>& adj, int src,
vector<int>& par) {
vector<int> dist(n, INT_MAX);
[Link](n, -1);
dist[src] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>,
greater<pair<int,int>>> pq; // MIN-heap of {dist, node}
[Link]({0, src});
while (![Link]()) {
auto [d, u] = [Link](); [Link]();
if (d > dist[u]) continue; // STALE entry -> skip
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) { // relaxation
dist[v] = dist[u] + w;
par[v] = u; // remember predecessor
[Link]({dist[v], v}); // no decrease-key in STL
}
}
}
return dist;
}
// rebuild the path src -> t:
vector<int> path;
for (int v = t; v != -1; v = par[v]) path.push_back(v);
reverse([Link](), [Link]());
5.7 Prim's MST — O(E log V) — grow ONE tree
int prim(int n, vector<vector<pair<int,int>>>& adj) {
vector<bool> inMST(n, false);
priority_queue<pair<int,int>, vector<pair<int,int>>,
greater<pair<int,int>>> pq; // {weight, node}
[Link]({0, 0}); // start from vertex 0
int total = 0;
while (![Link]()) {
auto [w, u] = [Link](); [Link]();
if (inMST[u]) continue; // already inside the tree
inMST[u] = true;
total += w;
for (auto [v, wt] : adj[u])
if (!inMST[v])
[Link]({wt, v}); // ONLY wt (Dijkstra pushes dist[u]+w!)
}
return total;
}
5.8 Kruskal's MST — O(E log E) — sort edges + Union-Find
#include <array>
vector<int> parent, rnk;
int findSet(int x) {
if (parent[x] != x)
parent[x] = findSet(parent[x]); // PATH COMPRESSION
return parent[x];
}
bool unite(int a, int b) {
int ra = findSet(a), rb = findSet(b);
if (ra == rb) return false; // same component -> would be a cycle
if (rnk[ra] < rnk[rb]) swap(ra, rb); // UNION BY RANK
parent[rb] = ra;
if (rnk[ra] == rnk[rb]) rnk[ra]++;
return true;
}
int kruskal(int n, vector<array<int,3>>& edges) { // each edge = {w, u, v}
sort([Link](), [Link]()); // ascending by weight
[Link](n); [Link](n, 0);
for (int i = 0; i < n; i++) parent[i] = i; // everyone is their own set
int total = 0, used = 0;
for (auto& [w, u, v] : edges) {
if (unite(u, v)) { // safe edge (no cycle)
total += w;
if (++used == n - 1) break; // tree complete
}
}
return total;
}
Tested on the 5-vertex weighted graph (edges 0-1:4, 0-2:1, 2-1:2, 1-3:1, 2-3:5, 3-4:3):
dijkstra from 0: 0 3 1 4 7 path to 4: 0 2 1 3 4
prim: 7 kruskal: 7 (always the same total)
Exam checklist for these codes
• Merge sort: <= in the merge keeps it stable; mid = lo + (hi-lo)/2 avoids overflow.
• Quick sort: partition returns the pivot's FINAL index; recursion excludes it.
• Monotonic stack: total work is O(n) — every index pushed once, popped once.
• BST delete, 2-children case: copy the inorder successor's key, then delete the successor from the right
subtree.
• Iterative DFS: the 'if (vis[u]) continue;' after popping is mandatory.
• Dijkstra: min-heap of {dist, node} (dist FIRST so the pair ordering works); skip stale entries.
• Prim vs Dijkstra: Prim pushes w, Dijkstra pushes dist[u] + w — one token difference, completely different
meaning.
• Kruskal: unite() returning false IS the cycle check; stop at n-1 accepted edges.