Algorithm VisionMaster Algorithms

L'algorithme de tri le plus basique qui compare à plusieurs reprises les éléments adjacents et les échange s'ils sont dans le mauvais ordre. Comme des bulles qui remontent à la surface, les valeurs plus grandes se déplacent progressivement vers la fin du tableau. Idéal pour les petits ensembles de données ou à des fins éducatives pour comprendre les fondamentaux du tri.

Trouve l'élément le plus petit et le déplace à l'avant de manière répétée. Chaque itération « sélectionne » le minimum parmi les éléments restants et le place après la partie triée. Simple à implémenter avec une utilisation minimale de la mémoire, mais prend toujours un temps O(n²) quelle que soit l'entrée.

Un algorithme de tri hautement efficace qui sélectionne un élément pivot et partitionne le tableau avec les valeurs plus petites à gauche et les plus grandes à droite. En moyenne O(n log n) et c'est la méthode de tri la plus utilisée en pratique. Forme la base des fonctions de tri intégrées dans la plupart des langages de programmation.

Utilise une structure de données de tas binaire en construisant d'abord un tas maximum, puis en extrayant à plusieurs reprises l'élément racine pour trier. Garantit une complexité temporelle O(n log n) dans tous les cas sans nécessiter de mémoire supplémentaire. Sert également de base aux implémentations de file de priorité.

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).

Un algorithme de division et conquête qui divise le tableau en deux, trie chaque moitié de manière récursive, puis les fusionne ensemble. Garantit un temps O(n log n) et est stable, mais nécessite de la mémoire supplémentaire. Particulièrement efficace pour les grands ensembles de données et le tri de listes chaînées.

Fonctionne comme le tri de cartes à jouer dans vos mains - insérant chaque élément un à la fois à sa position appropriée. S'exécute en temps O(n) pour les données déjà triées, ce qui le rend très efficace pour les petits tableaux ou les ensembles de données presque triés. Algorithme simple mais adaptatif.

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.

Méthode de recherche très efficace qui compare la cible avec l'élément du milieu et réduit de moitié l'espace de recherche de manière répétée. Avec un temps O(log n), elle peut trouver un élément parmi 1 million d'éléments en seulement 20 comparaisons. Fonctionne comme la recherche de mots dans un dictionnaire.

La méthode de recherche la plus basique qui vérifie chaque élément séquentiellement du début à la fin. Utilisée pour les données non triées ou les petits tableaux où la simplicité compte. L'implémentation est simple, mais devient lente avec de grands ensembles de données nécessitant un temps O(n).

Explore un graphe niveau par niveau, visitant tous les sommets à la profondeur actuelle avant d'aller plus profondément. Utilise une file d'attente et est idéal pour trouver les chemins les plus courts dans les graphes non pondérés. Les applications incluent la résolution de labyrinthes, l'analyse de réseaux sociaux et la recherche de connexions entre nœuds.

Explore un graphe en allant aussi profondément que possible le long de chaque chemin avant de revenir en arrière. Implémenté à l'aide d'une pile ou de la récursion, ce qui le rend naturel pour les problèmes récursifs. Utilisé pour la recherche de chemins, la détection de cycles, le tri topologique et la génération de labyrinthes.

Trouve les chemins les plus courts d'un sommet source unique vers tous les autres sommets dans un graphe pondéré. Alimente les systèmes de navigation GPS et les protocoles de routage réseau. Fonctionne efficacement avec des poids d'arêtes non négatifs en utilisant une approche gloutonne avec une file de priorité.

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.

Calcule efficacement les nombres de Fibonacci en utilisant la programmation dynamique pour éviter les calculs redondants. Démontre la puissance de la mémoïsation pour transformer une solution récursive en temps exponentiel en un algorithme en temps linéaire. Une introduction classique aux concepts de programmation dynamique.

Trouve la plus longue sous-séquence présente dans deux séquences dans le même ordre. Utilise la programmation dynamique pour construire une table de solution. Les applications incluent l'alignement de séquences ADN, les outils de différence de fichiers (diff) et la détection de plagiat.

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.