Ten Fundamental Algorithms: Sorting, Searching, Graph Traversal, and More

Algorithm 1: Quick Sort Quick Sort, developed by Tony Hoare, sorts n items with an average time complexity of O(n log n) and a worst‑case of O(n²), which is rare. It uses a divide‑and‑conquer strategy: choose a pivot, partition the list into elements less than and greater than the pivot, then recursively sort the sub‑lists. The recursion stops when sub‑lists contain zero or one element.

Algorithm 2: Heap Sort Heap Sort leverages the heap data structure, a nearly complete binary tree where each parent node satisfies the heap property (its key is greater than or less than its children). The algorithm builds a heap from the input array, repeatedly swaps the root (maximum) with the last element, reduces the heap size, and restores the heap property using a shift‑down operation, achieving O(n log n) average time.

Algorithm 3: Merge Sort Merge Sort is a classic divide‑and‑conquer sorting method. It recursively splits the array into two halves, sorts each half, and then merges the sorted halves by repeatedly selecting the smaller front element from the two sub‑arrays until all elements are merged.

Algorithm 4: Binary Search Binary Search finds a target value in a sorted array by repeatedly comparing the target with the middle element, discarding the half in which the target cannot lie, and continuing until the element is found or the sub‑array becomes empty. Its time complexity is O(log n).

Algorithm 5: BFPRT (Linear‑time Selection) BFPRT selects the k‑th smallest element in linear time even in the worst case. It groups the array into groups of five, finds each group's median (e.g., by insertion sort), recursively selects the median of medians as a pivot, partitions the array around this pivot, and then recurses into the appropriate partition.

Algorithm 6: Depth‑First Search (DFS) DFS explores a graph by moving as deep as possible along each branch before backtracking. Starting from a source vertex, it visits an unvisited neighbor recursively, using a stack (implicit via recursion) and can produce a topological ordering useful for many graph problems.

Algorithm 7: Breadth‑First Search (BFS) BFS traverses a graph level by level, using a queue to explore all neighbors of a vertex before moving to the next depth level. It is useful for finding the shortest path in unweighted graphs and for checking connectivity.

Algorithm 8: Dijkstra's Algorithm Dijkstra's algorithm computes the shortest paths from a source vertex to all other vertices in a directed graph with non‑negative edge weights. It repeatedly selects the vertex with the smallest tentative distance, relaxes its outgoing edges, and continues until all vertices are settled.

Algorithm 9: Dynamic Programming Dynamic programming solves problems with overlapping sub‑problems and optimal substructure by solving each sub‑problem once and storing its result. Typical steps include identifying the optimal substructure, formulating the recurrence relation, and building a table (bottom‑up) or using memoization (top‑down). The classic example is the knapsack problem.

Algorithm 10: Naive Bayes Classification Naive Bayes is a probabilistic classifier based on Bayes' theorem with the strong (naive) assumption that features are independent given the class label. It estimates class probabilities from training data and predicts the class with the highest posterior probability, performing well in many real‑world tasks despite its simplicity.