Algorithm Vision
Algorithmes de triIntermediate

Tri rapide

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.

#sorting#divide-and-conquer#in-place

Complexity Analysis

Time (Average)

O(n log n)

Expected case performance

Space

O(log n)

Memory requirements

Time (Best)

O(n log n)

Best case performance

Time (Worst)

O(n²)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 7•Section 7.1

Step: 1 / 0
500ms
SlowFast
Keyboard Shortcuts
Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%
Comparisons
0
Swaps
0
Array Accesses
0
Steps
1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default
Comparing
Swapped
Sorted

Code Execution

Currently executing
Previously executed

Implementation

Related Algorithms

View all in Algorithmes de tri

Tri à bulles

Beginner

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.

O(n²)
O(1)
sortingcomparison
Start Learning

Tri par sélection

Beginner

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.

O(n²)
O(1)
sortingcomparison
Start Learning

Tri par tas

Advanced

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

O(n log n)
O(1)
sortingheap
Start Learning
Back to Algorithmes de tri
Quick Sort - Algorithm Vision