Algorithm VisionMaster Algorithms

隣接する要素を繰り返し比較し、順序が間違っている場合に交換する最も基本的なソートアルゴリズムです。泡が水面に上がるように、大きな値が徐々に配列の末尾に移動します。小規模なデータセットやソートの基礎を理解するための教育目的に最適です。

最小の要素を見つけて繰り返し前方に移動させます。各反復で残りの要素から最小値を「選択」し、ソート済み部分の後ろに配置します。メモリ使用量は最小限でシンプルに実装できますが、入力に関係なく常にO(n²)の時間がかかります。

ピボット要素を選択し、小さい値を左側、大きい値を右側に配置して配列を分割する非常に効率的なソートアルゴリズムです。平均O(n log n)で、実際に最も広く使用されているソート方法です。ほとんどのプログラミング言語の組み込みソート関数の基盤となっています。

最大ヒープを構築し、ルート要素を繰り返し抽出してソートする二分ヒープデータ構造を使用します。すべての場合でO(n log n)の時間計算量を保証し、追加メモリを必要としません。優先度付きキューの実装の基礎にもなっています。

A non-comparison sorting algorithm that counts occurrences of each element and uses arithmetic to determine positions. Achieves O(n+k) time complexity where k is the range of input values. Ideal for sorting integers within a known, limited range. Forms the basis for radix sort.

A non-comparison sorting algorithm that processes elements digit by digit from least significant to most significant. Uses counting sort as a subroutine for each digit position. Achieves O(d(n+k)) time where d is the number of digits. Excellent for sorting integers or fixed-length strings.

An optimization of insertion sort that allows exchange of elements that are far apart. Uses a gap sequence that decreases to 1, enabling the algorithm to move elements closer to their final positions faster. Named after Donald Shell who invented it in 1959.

A distribution-based sorting algorithm that distributes elements into a number of buckets. Each bucket is then sorted individually using another sorting algorithm. Works best when input is uniformly distributed over a range. Average time complexity is O(n+k).

配列を半分に分割し、各半分を再帰的にソートしてから結合する分割統治アルゴリズムです。O(n log n)の時間を保証し、安定ですが、追加メモリが必要です。大規模なデータセットや連結リストのソートに特に効果的です。

手札のカードをソートするように、各要素を一度に適切な位置に挿入します。既にソート済みのデータに対してO(n)時間で実行されるため、小規模な配列やほぼソート済みのデータセットに非常に効率的です。シンプルながら適応的なアルゴリズムです。

Improvement over bubble sort that eliminates small values near the end of the list (turtles). Uses a shrinking gap sequence starting with array length, improving worst-case complexity. Practical for medium-sized datasets where simple implementation is valued over optimal performance.

Simple sorting algorithm similar to insertion sort, named after the way garden gnomes sort flower pots. Moves backward when elements are out of order, then forward again. While O(n²) like bubble sort, its simplicity makes it useful for teaching sorting concepts and handling small datasets.

目標値を中央の要素と比較し、探索空間を繰り返し半分にする非常に効率的な探索方法です。O(log n)時間で、100万個の要素からわずか20回の比較で項目を見つけることができます。辞書で単語を調べるように機能します。

最初から最後まで各要素を順番にチェックする最も基本的な探索方法です。未ソートデータや、シンプルさが重要な小規模配列に使用されます。実装は簡単ですが、O(n)時間を必要とする大規模データセットでは遅くなります。

グラフをレベルごとに探索し、より深く進む前に現在の深さのすべての頂点を訪問します。キューを使用し、重み付けされていないグラフでの最短経路を見つけるのに理想的です。迷路の解決、ソーシャルネットワーク分析、ノード間の接続の検索などの応用があります。

各経路に沿って可能な限り深く進んでから後戻りするグラフ探索方法です。スタックまたは再帰を使用して実装され、再帰的な問題に自然です。経路探索、サイクル検出、トポロジカルソート、迷路生成に使用されます。

重み付きグラフで単一始点から他のすべての頂点への最短経路を見つけます。GPSナビゲーションシステムやネットワークルーティングプロトコルを支えています。優先度付きキューを使用した貪欲法により、非負の辺の重みで効率的に機能します。

A best-first search algorithm that finds the shortest path using heuristics. Combines Dijkstra's algorithm and greedy best-first search using f(n) = g(n) + h(n). Widely used in games, robotics, and GPS navigation for efficient pathfinding.

Finds the Minimum Spanning Tree (MST) of a weighted undirected graph. Uses a greedy approach by sorting edges by weight and adding them if they don't create a cycle. Employs Union-Find for efficient cycle detection. Essential for network design and clustering.

Finds the Minimum Spanning Tree (MST) by growing a tree from a starting vertex. Always adds the minimum weight edge connecting a vertex in the tree to one outside. Uses a priority queue for efficient edge selection. Ideal for dense graphs.

Orders vertices of a Directed Acyclic Graph (DAG) such that for every edge u→v, u comes before v. Uses DFS-based approach. Essential for dependency resolution, build systems, and course scheduling.

Google's algorithm for ranking web pages by link structure. Computes importance scores iteratively.

Also known as the 'tortoise and hare' algorithm, this elegant technique detects cycles in linked lists or sequences using O(1) space. Uses two pointers moving at different speeds—if there's a cycle, they will eventually meet. Essential for detecting infinite loops, analyzing graph structures, and validating data integrity.

Single-source shortest path algorithm that handles negative weights and detects negative cycles. Relaxes all edges V-1 times to guarantee correct distances even with negative weights. Essential for currency arbitrage detection, network routing with varied costs, and situations where Dijkstra's algorithm fails. Trades speed for flexibility.

All-pairs shortest path algorithm that computes distances between every pair of vertices in O(V³) time. Uses dynamic programming with elegant three-line core logic. Handles negative weights and provides transitive closure. Ideal for dense graphs, network analysis, and when all pairwise distances are needed.

Greedy algorithm that builds a minimum spanning tree by adding edges in order of increasing weight, using union-find to avoid cycles. Efficient for sparse graphs with time complexity O(E log E). Applications include network design, clustering, approximation algorithms, and understanding greedy correctness proofs.

Greedy algorithm that grows a minimum spanning tree by repeatedly adding the cheapest edge connecting the tree to a new vertex. Uses a priority queue for efficiency with O(E log V) time. Preferred for dense graphs and real-time applications like network broadcasting and circuit design.

Knuth-Morris-Pratt algorithm for efficient pattern matching in strings. Uses a failure function (LPS array) to skip unnecessary comparisons, achieving O(n+m) time complexity. Essential for text search, DNA sequence analysis, and plagiarism detection.

Efficient string searching algorithm using bad character and good suffix heuristics. Compares pattern from right to left, allowing large jumps on mismatch. Achieves sublinear time in practice, making it one of the fastest string matching algorithms.

Finds the optimal way to parenthesize a chain of matrices to minimize the number of scalar multiplications. Classic dynamic programming problem from CLRS Chapter 15.

動的計画法を使用して冗長な計算を避けながらフィボナッチ数を効率的に計算します。メモ化の力を示し、指数時間の再帰的解を線形時間アルゴリズムに変換します。動的計画法の概念への古典的な入門です。

2つの列に同じ順序で存在する最長の部分列を見つけます。動的計画法を使用して解テーブルを構築します。DNA配列アライメント、ファイル差分ツール（diff）、盗作検出などの応用があります。

Dynamic programming algorithm that calculates the minimum number of single-character edits (insertions, deletions, substitutions) required to transform one string into another. Fundamental in spell checking, DNA sequence alignment, and natural language processing.

Classic dynamic programming problem where you must select items with given weights and values to maximize total value while staying within a weight capacity. Each item can only be taken once (0/1). Applications include resource allocation, portfolio optimization, and cargo loading.

Find the longest subsequence where all elements are in increasing order. Classic DP problem.

Elegant dynamic programming algorithm that finds the contiguous subarray with maximum sum in O(n) time. Combines greedy and DP principles by deciding at each step whether to extend the current subarray or start a new one. Essential for stock profit optimization, signal processing, and understanding DP optimization techniques.

Classic dynamic programming problem that finds the minimum number of coins needed to make a target amount. Demonstrates optimal substructure where the solution depends on solutions to smaller amounts. Widely applied in financial systems, vending machines, and resource allocation optimization.

Dynamic programming problem that finds the minimum number of cuts needed to partition a string into palindromic substrings. Uses DP to precompute which substrings are palindromes, then finds optimal cuts. Applications include text segmentation, DNA sequence analysis, and string optimization problems.

Place N chess queens on an N×N chessboard so no two queens threaten each other. A classic backtracking algorithm.

Find all prime numbers up to n by iteratively marking composites. Named after Eratosthenes of Cyrene (c. 276-194 BC).

Triangular array of binomial coefficients where each number is the sum of the two numbers directly above it. Named after Blaise Pascal (1623-1662), though known to mathematicians centuries earlier. Demonstrates beautiful mathematical patterns including binomial expansion, combinatorics, and connections to Fibonacci numbers.

Ancient algorithm from around 300 BC that efficiently computes the greatest common divisor of two integers. Based on the principle that GCD(a, b) = GCD(b, a mod b). One of the oldest algorithms in continuous use, forming the foundation of number theory, cryptography, and fraction simplification.

Extends the Euclidean algorithm to find integers x and y satisfying Bézout's identity: ax + by = GCD(a, b). Not only computes GCD but also finds the coefficients of linear combinations. Fundamental to modular arithmetic, RSA cryptography, and solving linear Diophantine equations.

Fundamental unsupervised machine learning algorithm for partitioning data into k clusters. Iteratively assigns points to nearest centroids and updates centroid positions. Widely used in customer segmentation, image compression, and exploratory data analysis.

Tree-based data structure that stores strings efficiently by sharing common prefixes. Each path from root to leaf represents a word or key. Excels at autocomplete, spell checking, IP routing tables, and dictionary implementations with O(m) operations where m is key length.

Finds the deepest node that is an ancestor of two given nodes in a tree. Fundamental operation in tree queries with applications in computational biology (species evolution), network routing, and version control systems. Various algorithms offer different time-space tradeoffs.

First self-balancing binary search tree invented in 1962 by Adelson-Velsky and Landis. Maintains height balance through rotations, guaranteeing O(log n) operations. Stricter balancing than red-black trees makes it ideal for lookup-heavy applications like databases and file systems.

Select the maximum number of non-overlapping activities. Classic greedy algorithm that always picks the activity finishing earliest.