Master 10 Essential Algorithms: From QuickSort to Naive Bayes

Algorithm 1: Quick Sort

Quick sort is a divide‑and‑conquer sorting algorithm developed by Tony Hoare. It sorts n items with an average time complexity of O ( n log n ) and a worst‑case of O ( n 2 ). The algorithm works by selecting a pivot , partitioning the list into elements smaller and larger than the pivot, and then recursively sorting the sub‑lists. The recursion stops when the sub‑list size is zero or one.

Algorithm 2: Heap Sort

Heap sort uses a 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 average time complexity is O ( n log n ). Steps:

Create a heap H[0..n‑1].

Swap the root (maximum) with the last element.

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

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

Algorithm 3: Merge Sort

Merge sort (also called “合并排序”) is a classic divide‑and‑conquer sorting method. Steps:

1. Allocate auxiliary space equal to the sum of the two sorted sub‑sequences. 2. Set two pointers at the beginnings of the two sorted sequences. 3. Compare the elements pointed to, move the smaller one into the auxiliary space, and advance that pointer. 4. Repeat step 3 until one pointer reaches the end of its sequence. 5. Copy the remaining elements of the other sequence to the end of the merged array.

Algorithm 4: Binary Search

Binary search finds a target element in a sorted array by repeatedly halving the search interval. Each comparison reduces the range by half, yielding a time complexity of O (log n ).

Algorithm 5: BFPRT (Linear Selection)

The BFPRT algorithm selects the k‑th smallest element in linear time, even in the worst case. Steps:

1. Divide the n elements into groups of five. 2. Find the median of each group (e.g., by insertion sort). 3. Recursively select the median of these medians, call it x. 4. Partition the array around x; let k be the number of elements ≤ x. 5. If i == k, return x; if i < k, recursively select the i‑th smallest in the left part; otherwise, select the (i‑k)-th smallest in the right part. Termination occurs when the sub‑array size is 1.

Algorithm 6: Depth‑First Search (DFS)

DFS explores a graph by moving as deep as possible along each branch before backtracking. Steps:

1. Visit a vertex v. 2. From v, recursively explore each unvisited adjacent vertex. 3. When all reachable vertices from v are visited, backtrack to the most recent vertex with unvisited neighbors and continue. The process repeats until all vertices are visited.

Algorithm 7: Breadth‑First Search (BFS)

BFS traverses a graph level by level using a queue.

Steps:

Enqueue the root vertex.

Dequeue a vertex and check if it is the target.

If not, enqueue all its unvisited direct neighbors.

If the queue becomes empty, the target does not exist.

Repeat steps 2‑4.

Algorithm 8: Dijkstra's Algorithm

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

Steps:

1. Initialize set S with the source vertex V0; set T with the remaining vertices. For each vertex in T, assign distance d(V0,Vi) = weight of edge (V0,Vi) if it exists, otherwise ∞. 2. Select the vertex W in T with the smallest distance value and move it to S. 3. For each vertex remaining in T, update its distance if a shorter path through W is found. Repeat steps 2‑3 until T is empty.

Algorithm 9: Dynamic Programming

Dynamic programming solves complex problems by breaking them into overlapping subproblems and storing intermediate results.

Key steps:

1. Identify optimal substructure – the optimal solution contains optimal solutions to subproblems. 2. Recognize overlapping subproblems – solve each subproblem once and reuse its result. 3. Build a table (bottom‑up) or use memoization (top‑down) to store solutions.

Algorithm 10: Naive Bayes Classification

Naive Bayes is a probabilistic classifier based on Bayes’ theorem with the strong (naive) assumption that features are conditionally independent given the class.

It estimates class probabilities from training data and predicts the class with the highest posterior probability. Despite its simplicity, it performs well in many real‑world tasks.