Tag: Algorithms
Quick Select
QuickSelect finds the k-th smallest element (0-based) in expected linear time by repeatedly partitioning the array in-place, shrinking the search to the side that must contain the answer.
Bottom-Up Merge Sort
An iterative (non-recursive) merge sort that repeatedly merges adjacent sorted runs of size 1, 2, 4, … until the whole array is sorted.
Shell Sort
An in-place generalization of insertion sort that improves performance by comparing elements far apart using gap-based passes, achieving sub-quadratic time in practice.
Top-Down Merge Sort
A stable divide-and-conquer sort that recursively splits an array, then merges sorted halves using a single auxiliary array.
LRU Cache
A fixed-capacity cache that guarantees O(1) access and eviction by combining a HashMap for lookup with a doubly linked list for usage ordering.
Dijkstra’s Shortest Path Algorithm
Single-source shortest path algorithm for graphs with non-negative edge weights.
Breadth-First Search on an Adjacency Matrix
Level-order traversal over a graph represented as a matrix, with shortest-path reconstruction.
Depth-First Search (DFS) on an Adjacency List
Recursive DFS to find a path between two vertices using an adjacency list representation.
Tree Comparison
Structural comparison requires explicit null tracking. DFS naturally enforces this through recursion, while BFS requires careful handling of null positions.
Breadth-First Search
Level-order traversal with guarantees DFS cannot make.
Tree Traversal
Three traversal orders over the same structure, each revealing a different meaning.
Binary Search Tree
A comparison-based tree offering logarithmic operations when balanced, and linear ones when not.
QuickUnion
A near-constant time solution to dynamic connectivity using weighted trees and path compression.
PriorityQueue
A queue optimized for fast access to the highest-priority element.
UnionFind
A different view on the dynamic connectivity problem through the lens of Quick-Find.
Bubble Sort
A quadratic-time algorithm that’s only useful as a teaching tool — but still has a few subtle properties.
Insertion Sort
A simple O(n²) sorting algorithm that is surprisingly fast on small or nearly sorted arrays.
Quick Sort
A divide-and-conquer sorting algorithm with excellent average performance and a dangerous worst case.
Selection Sort
A simple O(n²) sorting algorithm with predictable behavior — and consistently poor performance.
Binary Search in Less Than a Minute
A simple algorithm whose correctness depends on precise invariants.