Scribd
Importer
8 vues2 pages

Algorithmes de tri : types et complexité

Le document traite des algorithmes de tri, expliquant leur importance dans l'organisation et l'analyse des données. Il présente différents types d'algorithmes, notamment les tris par comparaison et linéaires, ainsi que leur complexité algorithmique. Des exemples de pseudo-code pour le tri à bulles et le tri par sélection sont également fournis.

Transféré par

light 667
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
8 vues2 pages

Algorithmes de tri : types et complexité

Le document traite des algorithmes de tri, expliquant leur importance dans l'organisation et l'analyse des données. Il présente différents types d'algorithmes, notamment les tris par comparaison et linéaires, ainsi que leur complexité algorithmique. Des exemples de pseudo-code pour le tri à bulles et le tri par sélection sont également fournis.

Transféré par

light 667
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Les algorithmes de tri

1. Le concept
1.1 Le besoin
Le tri est une opération courante dans de nombreuses applications et des algorithmes efficaces
ont été développés pour l'effectuer.
Le tri est le processus qui consiste à organiser les données dans un ordre significatif afin de
pouvoir les analyser plus efficacement.
Le tri de données vous permet de visualiser rapidement vos données et de les comprendre,
d'organiser et de rechercher des données précises et, à terme, de prendre des décisions
avec plus d'efficacité.

1.2 Les types de tri


Wikipedia répertorie 43 algorithmes de tri différents. Tri rapide, tri par fusion, tri par coquille
différentes circonstances., tri à bulles, tri par casiers, tri par répartition, tri par billes, tri par
comparateur, et bien d'autres encore. Pourquoi autant ? Parce que différents algorithmes de tri
sont utiles dans

2. La pratique
2.1 Tri par comparaison
a. Les tris naïfs
i. Tri à bulles (bubble sort) ou par propagation
ii. Par sélection ou par extraction
iii. Par insertion
b. Diviser pour régner
i. Tri fusion
ii. Tri rapide (Quick Sort) ou tri pivot

2.2 Tri linéaire


c. Par dénombrement
d. Par parquet
e. Par base

3. Complexité
La complexité algorithmique est un concept très important qui permet de comparer les
algorithmes afin de trouver celui qui est le plus efficace.
L'analyse de la complexité d'un algorithme consiste en l'étude formelle de la quantité de
ressources (par exemple de temps ou d'espace) nécessaire à l'exécution de cet algorithme.
Le pseudo-code du tri à bulles
T : tableau
N : entier //Taille réelle du tableau
j, i : entier //Compteurs
POUR i 1 à N-1 FAIRE
POUR j i+1 à N FAIRE
SI T[j] > T[i] ALORS
//Permutation T[j] et T[i]
FSI
FPOUR
FPOUR

Le pseudo-code du tri par sélection


T : tableau
N : entier //Taille réelle du tableau
j, i, sel : entier //Compteurs
POUR i 1 à N-1 FAIRE
sel  i
POUR j i+1 à N FAIRE
SI T[j] > T[sel] ALORS
sel  j
FSI
FPOUR
SI sel != i ALORS
//Permutation T[i] et T[sel]
FSI
FPOUR

[1] Beauquier, Berstel et Chretienne, Éléments d’algorithmique.


[2] Cormen, Algorithmique.
[3] Froidevaux, Gaudel et Soria, Types de données et algorithmes.

[Link]

Vous aimerez peut-être aussi