Master 10 Essential Algorithms: From QuickSort to Naive Bayes

Algorithm 1: QuickSort

QuickSort, developed by Tony Hoare, sorts n items with an average time complexity of O(n log n) and a worst‑case of O(n²), though the worst case is rare. It uses a divide‑and‑conquer approach.

Select a pivot element from the list.

Partition the list so that elements smaller than the pivot come before it and larger elements come after it.

Recursively apply QuickSort to the sub‑lists on each side of the pivot.

The recursion stops when sub‑lists contain zero or one element, which are already sorted.

Algorithm 2: HeapSort

HeapSort leverages the heap data structure (a nearly complete binary tree) where each parent node satisfies the heap property relative to its children.

Its average time complexity is O(n log n).

Build a heap H[0..n‑1] from the input array.

Swap the root (maximum) with the last element of the heap.

Reduce the heap size by one and call shift_down(0) to restore the heap property.

Repeat steps 2‑3 until the heap size becomes 1.

Algorithm 3: MergeSort

MergeSort is a classic divide‑and‑conquer sorting algorithm that repeatedly merges sorted sub‑lists.

Allocate auxiliary space equal to the combined size of the two sorted sub‑lists.

Initialize two pointers at the start of each sorted sub‑list.

Compare the pointed elements, copy the smaller one into the auxiliary space, and advance that pointer.

When one sub‑list is exhausted, copy the remaining elements of the other sub‑list.

Algorithm 4: Binary Search

Binary Search finds a target element in a sorted array by repeatedly halving the search interval, achieving O(log n) time complexity.

Algorithm 5: BFPRT (Linear Selection)

BFPRT selects the k‑th smallest element in linear time, even in the worst case, using a median‑of‑medians strategy similar to QuickSort.

Group the n elements into ⌈n/5⌉ groups of five.

Find the median of each group (e.g., by insertion sort).

Recursively select the median of these medians; call it x.

Partition the array around x, counting elements ≤ x (k) and > x (n‑k).

If i = k, return x; if i < k, recurse on the left partition; otherwise recurse on the right partition with i‑k.

Base case: when n = 1, the single element is the answer.

Algorithm 6: Depth‑First Search (DFS)

DFS explores a graph by traversing as deep as possible along each branch before backtracking, producing a depth‑first ordering and enabling topological sorting.

Visit a vertex v.

Recursively visit each unvisited neighbor of v.

If unvisited vertices remain, start a new DFS from one of them.

Algorithm 7: Breadth‑First Search (BFS)

BFS explores a graph level by level using a queue, guaranteeing that the shortest‑path distance (in edges) from the start vertex to any visited vertex is found.

Enqueue the root vertex.

Dequeue a vertex, check if it is the goal; if not, enqueue all its unvisited neighbors.

Repeat until the queue is empty (goal not found) or the goal is found.

Algorithm 8: Dijkstra's Shortest‑Path

Dijkstra's algorithm computes the shortest paths from a source vertex S to all other vertices in a directed graph with non‑negative edge weights.

Initialize set S with the source vertex; set distances of all other vertices to ∞ (or to the weight of the edge from S if it exists).

Select the vertex W outside S with the smallest tentative distance and add it to S.

For each neighbor of W, update its distance if a shorter path through W is found.

Repeat steps 2‑3 until all vertices are included in S.

Algorithm 9: Dynamic Programming

Dynamic programming solves complex problems by breaking them into overlapping sub‑problems, solving each once, and storing the results.

Identify optimal sub‑structure: optimal solutions to sub‑problems compose an optimal solution to the whole problem.

Exploit overlapping sub‑problems: compute each sub‑problem once and cache its result.

Classic example: the knapsack problem.

Algorithm 10: Naive Bayes Classification

Naive Bayes is a probabilistic classifier based on Bayes' theorem with the simplifying assumption that features are conditionally independent given the class.

It estimates class probabilities from training data (often using maximum likelihood) and predicts the class with the highest posterior probability.