Section courante

A propos

Section administrative du site

 Langage  Elément  Programmation  Annexe  Aide 
ABAP/4
Ada
Assembleur
Assembly & bytecode
ASP (Active Server Pages)
Basic
C
C++
C# (C Sharp)
Cobol
ColdFusion
Fortran
HTML
Java
JavaScript
LISP
Logo
LotusScript
Oberon
Pascal
Perl
PHP
PL/1
Prolog
Python
Rebol
REXX
Ruby
Rust
SAS
NoSQL
SQL
Swift
X++ (Axapta)
GNAT
SMALLAda
VHDL
Assembleur 370
Assembleur 1802
Assembleur 4004
Assembleur 6502
Assembleur 6800
Assembleur 68000
Assembleur 8080 et 8085
Assembleur 8089
Assembleur 80x86
Assembleur AGC4
Assembleur ARM
Assembleur DPS 8000
Assembleur i860
Assembleur Itanium
Assembleur MIPS
Assembleur PDP-11
Assembleur PowerPC
Assembleur RISC-V
Assembleur SPARC
Assembleur SuperH
Assembleur UNIVAC I
Assembleur VAX
Assembleur Z80
Assembleur Z8000
Assembleur z/Architecture
ASSEMBLER/MONITOR 64
Micol Assembler
GFA Assembler
A86
MASM (Macro Assembler)
TASM (Turbo Assembler)
CIL
Jasmin
LLVM
MSIL
Parrot
P-Code (PCode)
SWEET16
G-Pascal
ASP 1.0
ASP 2.0
ASP 3.0
ASP.NET
ASP.NET Core
ABasiC (Amiga)
Adam SmartBASIC
Altair BASIC
AmigaBASIC (Amiga)
AMOS Basic (Amiga)
Atari Basic (Atari 400, 600 XL, 800, 800XL)
Basic Apple II (Integer BASIC/APPLESOFT)
Basic Commodore 64 (CBM-BASIC)
Basic Commodore 128 (BASIC 7.0)
Basic Commodore VIC-20 (CBM-BASIC 2.0)
Basic Coco 1 (Color Basic)
Basic Coco 2 (Extended Color Basic)
Basic Coco 3 (Extended Color Basic 2.0)
BASICA (PC DOS)
Basic Pro
BBC BASIC
Blitz BASIC (Amiga)
DarkBASIC
Dartmouth BASIC
GFA-Basic (Atari ST/Amiga)
GWBASIC (MS-DOS)
Liberty BASIC
Locomotive BASIC (Amstrad CPC)
MSX-Basic
Omikron Basic (Atari ST)
Oric Extended Basic
Power Basic
Quick Basic/QBasic (MS-DOS)
Sinclair BASIC (ZX80, ZX81, ZX Spectrum)
ST BASIC (Atari ST)
Turbo Basic
Vintage BASIC
VBScript
Visual Basic (VB)
Visual Basic .NET (VB .NET)
Visual Basic pour DOS
Yabasic
BeckerBASIC
SIMONS' BASIC
Basic09 d'OS-9
Disk Extended Color Basic
Basic09 d'OS-9
Disk Extended Color Basic
Access
Excel
Visual Basic pour Windows
Visual Basic .NET pour Windows
C Shell Unix (csh)
C pour Amiga
C pour Atari ST
C pour DOS
C pour Falcon030
C pour GEMDOS (Atari ST)
C pour Linux
C pour PowerTV OS
C pour OS/2
C pour Unix
C pour Windows
Aztec C
CoCo-C
GNU C
HiSoft C
IBM C/2
Introl-C
Lattice C
Microsoft C
MinGW C
MSX-C
Open Watcom C
OS-9 C Compiler
Pure C
Quick C
Turbo C
HiSoft C for Atari ST
HiSoft C for CP/M (Amstrad CPC)
C++ pour OS/2
C++ pour Windows
Borland C++
C++Builder
IBM VisualAge C++
Intel C++
MinGW C++
Open Watcom C++
Symantec C++
Turbo C++
Visual C++
Visual C++ .NET
Watcom C++
Zortech C++
C# (C Sharp) pour Windows
Apple III Cobol
Microsoft Cobol
BlueDragon
Lucee
OpenBD
Railo
Smith Project
Microsoft Fortran
WATFOR-77
CSS
FBML
Open Graph
SVG
XML
XSL/XSLT
LESS
SASS
GCJ (GNU)
JSP
Jython
Visual J++
Node.js
TypeScript
AutoLISP
ACSLogo
LotusScript pour Windows
Amiga Oberon
Oberon .NET
Apple Pascal
Delphi/Kylix/Lazarus
Free Pascal
GNU Pascal
HighSpeed Pascal
IBM Personal Computer Pascal
Lisa Pascal
Maxon Pascal
MPW Pascal
OS-9 Pascal
OSS Personal Pascal
Pascal-86
Pascal du Cray Research
Pascal/VS
Pascal-XT
PURE Pascal
QuickPascal
RemObjets Chrome
Sun Pascal
THINK Pascal
Tiny Pascal (TRS-80)
Turbo Pascal
UCSD Pascal
VAX Pascal
Virtual Pascal
Turbo Pascal for CP/M-80
Turbo Pascal for DOS
Turbo Pascal for Macintosh
Turbo Pascal for Windows
CodeIgniter (Cadre d'application)
Drupal (Projet)
Joomla! (Projet)
Phalanger (PHP .NET)
phpBB (Projet)
Smarty (balise)
Twig (balise)
Symfony (Cadre d'application)
WordPress (Projet)
Zend (Cadre d'application)
PL360
PL/M-80
PL/M-86
Turbo Prolog
CPython
IronPython
Jython
PyPy
AREXX
Regina REXX
JMP
Btrieve
Cassandra
Clipper
CouchDB
dBASE
Hbase
Hypertable
MongoDB
Redis
Access
BigQuery
DB2
H2
Interbase
MySQL
Oracle
PostgreSQL
SAP HANA
SQL Server
Sybase
U-SQL
Introduction
Historique
Les remarques
Les opérateurs
Les conditionnelles
Les algorithmes à base logarithmique
Les algorithmes sur les tris
Les algorithmes sur la recherche
Les algorithmes sur l'affichage
Les algorithmes sur les mathématiques
Les algorithmes de traitement de chaînes de caractères
Les algorithmes de cryptographie
Les algorithmes de traitement de graphes
Les algorithmes de traitement d'image et de vision par ordinateur
Les algorithmes d'intelligence artificielle et d'apprentissage automatique
Les algorithmes d'optimisation
Les algorithmes sur les fractals
Les algorithmes de traitement de dates et de temps
Les algorithmes de compression
Les algorithmes sur le gouvernement ou la réglementation
Tri à bulles (Bubble Sort)
Tri par insertion (Insertion Sort)
Tri par sélection (Selection Sort)
Tri de Shell-Metzner
Recherche séquentielle (Recherche linéaire)
Recherche dichotomique (Recherche binaire)
Algorithmes de calcul numérique
Algorithmes de calcul matriciel et algèbre linéaire
Algorithmes mathématiques de géométrie et trigonométrie
Algorithmes de théorie des nombres
Algorithmes statistiques et probabilistes
Algorithmes de calcul scientifique et d'optimisation
Triangle de Sierpinski
Année bissextile
Calcul de la différence entre deux dates
Algorithmes de fiscalité
Algorithmes de gestion des prestations sociales
Téléphone
Préface
Notes légal
Dictionnaire
Recherche

Introduction

Les algorithmes de tri sont des méthodes pour organiser les éléments d'une liste, d'un tableau, ou d'une structure de données dans un certain ordre, généralement croissant ou décroissant. Ils sont fondamentaux en informatique, car de nombreux programmes ont besoin de trier des données pour des recherches, des analyses, ou des affichages efficaces. Les principaux objectifs des algorithmes de tri sont l'efficacité (rapidité), la stabilité (conservation de l'ordre relatif des éléments), et la simplicité (facilité de mise en oeuvre).

Types principaux d'algorithmes de tri

Voici les principaux types d'algorithmes de tri :

Critères d'évaluation des algorithmes de tri

Voici les principaux critères d'évaluation des algorithmes de tri :

Utilisation des algorithmes de tri

Les algorithmes de tri sont utilisés dans diverses applications, comme le tri des bases de données, le traitement des images, le tri des fichiers pour les systèmes de fichiers, ou l'organisation des informations pour des opérations de recherche optimisées.

Chaque algorithme a ses avantages et inconvénients selon les caractéristiques des données et les exigences de performance.


Les algorithmes de tri

Les algorithmes de tri permettent de mettre en ordre alphabétique ou numérique différents éléments contenu dans un tableau. Voici différents algorithmes en lien avec le tri, comme par exemple : tri à bulles, tri de shell, tri par échange, tri par extraction, tri par insertion, tri sélection, tri QuickSort,...

Tri à bulles

Le tri à bulles (ou tri par bulles en français, ou encore bubble sort en anglais) est un algorithme de tri simple organisant une liste en comparant successivement des paires d'éléments adjacents et en les échangeant si nécessaire. Le processus répète ce balayage jusqu'à ce que la liste soit entièrement triée.

Principe de fonctionnement

Complexité et limites

Algorithme

L'idée derrière cette technique est très simple, parcourir le tableau et permuter deux éléments lorsque cela s'avère nécessaire. Voici son algorithme :

BOUCLE POUR INombre d'élément - 2 JUSQU'A 0 PAS -1 FAIRE
   BOUCLE POUR J ← 0 JUSQU'A I PAS 1 FAIRE
      SI Tableau [J + 1] < Tableau [J] ALORS
         Échanger Tableau [J + 1] avec Tableau [J]
      FIN SI
   FIN BOUCLE POUR
FIN BOUCLE POUR

Tri de Shell-Metzner

Le tri de Shell-Metzner, ou plus simplement tri de Shell (du nom de son inventeur Donald Shell en 1959), est une amélioration du tri par insertion, conçue pour augmenter son efficacité sur les grandes listes. Il fonctionne en divisant la liste à trier en sous-séries d'éléments séparés par un certain écart (ou "gap"), diminuant progressivement. Au sein de chaque sous-série, les éléments sont triés localement. Au fur et à mesure que l'écart est réduit, les sous-séries se rapprochent, jusqu'à ce que l'écart atteigne 1, ce qui équivaut à un tri par insertion final sur la liste entière. Ce procédé permet de déplacer rapidement les éléments sur de longues distances, ce qui accélère la convergence vers une liste triée.

Principe du tri de Shell-Metzner

Avantages et complexité

Le tri de Shell-Metzner est plus rapide que le tri par insertion traditionnel, notamment sur de grands ensembles de données, bien qu'il ait une complexité de temps variable en fonction de la séquence d'écarts choisie. Certaines séquences, comme celles de Hibbard ou de Sedgewick, améliorent son efficacité, réduisant la complexité temporelle dans le meilleur des cas à environ O(n3/2) voire moins avec certaines optimisations.

Algorithme

La technique de tri nommée «Shell-Metzner», est en fait une technique de réduction du nombre de comparaison a effectuer pour trier un tableau. Comment si prend-on? C'est simple, la comparaison s'effectue entre 2 éléments séparer par un écart égal (au départ) à la moitié de la taille du tableau. Ensuite, la comparaison s'effectue entre des éléments séparées par un écart égal au nombre d'élément du tableau divisée par 4. Lorsque l'écart atteint finalement 1, la tri est terminer.

ÉcartNombre d'élément
BOUCLE FAIRE
   ÉcartÉcart / 2
   BOUCLE FAIRE
      Inversion ← Faux
      BOUCLE POUR I ← 1 JUSQU'A Nombre d'élément - Écart
         JI + Écart
         SI Tableau [J] < Tableau [I] ALORS
            TemporaireTableau[I]
            Tableau[I] ← Tableau[J]
            Tableau[J] ← Temporaire
            Inversion ← Vrai
         FIN SI
      FIN BOUCLE POUR
   TANT QUE N'EST PAS Inversion
TANT QUE Écart = 1

Tri par échange

La technique de tri par échange consiste a comparer un premier élément avec un autre et lorsqu'il trouve un élément plus petit, un échange est effectuer avec ce premier élément. De cette façon, on finira par placer cette élément correctement. Ensuite, on recommence avec le 2ième élément jusqu'à la fin. En voici l'algorithme:

BOUCLE POUR I ← 0 JUSQU'A Nombre d'élément - 2 PAS 1 FAIRE
* Comparer avec les autres éléments.
   BOUCLE POUR JI + 1 JUSQU'A Nombre d'élément - 1 PAS 1 FAIRE
      SI Tableau [I] > Tableau [ J ] ALORS
         Échanger Tableau [ J ] avec Tableau [ I ]
      FIN SI
   FIN BOUCLE POUR
FIN BOUCLE POUR

Tri par extraction

La tri par extraction est une consiste a tout d'abord trouver le plus élément d'un tableau et de l'échanger avec le premier indice de celui, soit habituellement l'indice 0. Par la suite, il poursuit ses recherches d'un élément minimum entre l'élément 1 à celle de la fin. Il effectuera se traitement jusqu'à terme. Voici donc l'algorithme:

BOUCLE POUR K ← 0 JUSQU'A Nombre d'élément - 2 PAS 1 FAIRE
   Position MinimumK
   BOUCLE POUR JK + 1 JUSQU'A N – 1
      SI Tableau [ J ] < Tableau [ Position Minimum] ALORS Position MinimumJ
   BOUCLE FIN POUR
   SI Position MinimumK ALORS
      Échanger Tableau[K] avec Tableau[Position Minimum]
   FIN SI
FIN BOUCLE POUR

Tri par insertion

La tri par insertion comme son nom l'indique consiste à prendre le premier élément en commençant par le deuxième et d'ensuite de l'insérer directement à la place approprié dans les indices situés entre 0 et I. Voici donc son algorithme:

BOUCLE POUR I ← 1 JUSQU'A Nombre d'élément - 1 PAS 1 FAIRE
   BOUCLE POUR J ← 0 JUSQU'A I - 1 PAS 1 FAIRE
      SI Tableau [ I ] <= Tableau [ J ] ALORS
         Temporaire Tableau [ I ] * L'élément à insérer
         BOUCLE POUR K I - 1 JUSQU'A J PAS -1 FAIRE * Faire de la place.
            Tableau [ K + 1 ] ← Tableau [ K ]
         FIN POUR
         Tableau [ J ] ← Temporaire * Insère l'élément.
         QUITTER BOUCLE * Fin de la deuxième boucle.
      FIN SI
   FIN BOUCLE POUR
FIN BOUCLE POUR

Tri par sélection

La tri par sélection est une technique très intéressante, en effet, contrairement à la Tri à bulles ou par échanges, elle sélectionne systématiquement le plus petit élément et échange celui-ci avec le premier élément de la liste. Ensuite, il applique cette même manière de procéder avec le 2ième élément jusqu'à la fin de la liste. En voici l'algorithme :

BOUCLE POUR I ← 0 JUSQU'A Nombre d'élément - 2 PAS 1 FAIRE
   PositionI
   TemporaireTableau [ I ]
   * Chercher le plus petit élément à partir de la position «I»
   BOUCLE POUR JI + 1 JUSQU'A Nombre d'élément - 1 PAS 1 FAIRE
      SI Tableau [J ] < Temporaire ALORS
         PositionJ
         TemporaireTableau [ J ]
      FIN SI
   FIN BOUCLE POUR
   * Mettre le plus petit élément à la position «I»
   Tableau [ Position ] ← Tableau [ I ]
   Tableau [ I ] ← Temporaire
FIN BOUCLE POUR

Tri par QuickSort

Le «QuickSort» est sans nulle doute la technique de tri la plus rapide. Le seul inconvénient de cette technique c'est qu'elle empile un grand nombre d'élément dans la pile, on ne pourra donc pas l'employer par exemple pour une base de données sollicitant des millions d'informations. Toutefois, elle pourra être utilise en graphisme par exemple. Voici l'algorithme de cette technique de tri:

MODULE QuickSort ( référence A,valeur L,valeur R )
   IL
   JR
   XA [ ( L + R ) / 2 ]
   BOUCLE FAIRE TANT QUE I < J
      BOUCLE FAIRE TANT QUE A [ I ] < X
         II + 1
      FIN BOUCLE TANT QUE
      BOUCLE FAIRE TANT QUE X < A [ J ]
         JJ + 1
      FIN BOUCLE TANT QUE
      SI IJ ALORS
         Échange A [ I ] et A [ J ]
         II + 1
         JJ + 1
      FIN SI
   FIN BOUCLE TANT QUE
   SI L < J ALORS
      QuickSort( A, L, J )
   FIN SI
   SI I < R ALORS
      QuickSort ( A, I, R )
   FIN SI


PARTAGER CETTE PAGE SUR
Dernière mise à jour : Dimanche, le 12 mars 2006