Algorithmes de triAdvanced

Tri par base

Un algorithme de tri non comparatif qui traite les éléments chiffre par chiffre du moins significatif au plus significatif. Utilise le tri par comptage comme sous-routine pour chaque position de chiffre. Atteint un temps O(d(n+k)) où d est le nombre de chiffres. Excellent pour trier des entiers ou des chaînes de longueur fixe.

#sorting#linear-time#non-comparison#stable#digit-based

Complexity Analysis

Time (Average)

O(d * n)

Expected case performance

Space

O(n + k)

Memory requirements

Time (Best)

O(d * n)

Best case performance

Time (Worst)

O(d * n)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 8•Section 8.3

Input Array (non-negative integers 0-999, max 12 elements)

Quick Presets:

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

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.

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.

Tri rapide

Intermediate

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.

O(n log n)

O(log n)

sortingdivide-and-conquer

Start Learning

Back to Algorithmes de tri