Overview of Ten Classic Algorithms: Sorting, Searching, Graph Traversal, and Machine Learning

Quick Sort, developed by Tony Hoare, sorts n items with an average time complexity of O(n log n) by selecting a pivot, partitioning the list into elements smaller and larger than the pivot, and recursively sorting the sub‑lists; its worst case O(n²) is rare.

Heap Sort leverages a heap data structure (an almost complete binary tree where each child key is less or greater than its parent) to achieve O(n log n) average complexity; it builds a heap, repeatedly swaps the root with the last element, reduces the heap size, and performs a shift‑down operation until the heap is empty.

Merge Sort is a divide‑and‑conquer algorithm that recursively splits a list, then merges sorted sub‑lists by allocating space, using two pointers to compare elements, copying the smaller element into the merged array, and finally appending any remaining elements.

Binary Search finds a target element in a sorted array by repeatedly comparing the middle element and discarding half of the remaining interval, achieving O(log n) time complexity.

BFPRT (linear selection) finds the k‑th smallest element in worst‑case linear time by grouping elements into fives, finding each group's median, selecting the median of medians as a pivot, partitioning around it, and recursively searching the appropriate partition.

Depth‑First Search (DFS) explores a graph by moving as deep as possible along each branch before backtracking, producing a traversal order (often used for topological sorting) and typically implemented with recursion or an explicit stack.

Breadth‑First Search (BFS) explores a graph level by level using a queue, ensuring that all vertices at a given distance from the start are visited before moving deeper, and is useful for shortest‑path searches in unweighted graphs.

Dijkstra’s algorithm computes single‑source shortest paths in a directed graph with non‑negative edge weights by repeatedly selecting the unvisited vertex with the smallest tentative distance, relaxing its outgoing edges, and continuing until all vertices are processed.

Dynamic Programming solves problems by breaking them into overlapping subproblems, storing intermediate results (memoization), and exploiting optimal substructure; classic examples include the knapsack problem and many combinatorial optimization tasks.

Naive Bayes classification applies Bayes’ theorem under the assumption that features are conditionally independent, providing a simple probabilistic model that can be trained with maximum‑likelihood estimation and used for various supervised learning tasks.