Forum programmation
 
AccueilPortailFAQRechercherS'enregistrerMembresGroupesConnexion

Partagez | 
 

 Algorithme de tri

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Algorithme de tri   Ven 9 Fév - 15:21

En informatique ou en mathématiques, un algorithme de tri est un algorithme qui permet d'organiser une collection d'objets selon un ordre déterminé. Les objets à trier font donc partie d'un ensemble muni d'une relation d'ordre (de manière générale un ordre total). Les ordres les plus utilisés sont l’ordre numérique et lexicographique (dictionnaire).
Il est évident que suivant la relation d'ordre considérée, une même collection d’objet peut donner lieu à divers arrangements, pourtant il est possible de définir un algorithme de tri indépendamment de la fonction d’ordre utilisée. Celui-ci ne fera qu'utiliser une certaine fonction d’ordre correspondante à une relation d’ordre qui doit permettre de comparer tout couple d'éléments de la collection.

Classification

La classification des algorithmes de tri est très importante, car elle permet de choisir le type d’algorithme le plus adapté au problème traité, tout en tenant compte des contraintes imposées par celui-ci.
On distingue, tout d'abord, les algorithmes de tri d'application générale, procédant par comparaisons entre des paires d'éléments, d'algorithmes plus spécialisés faisant des hypothèses restrictives sur la structure des données entrées (par exemple, le tri par comptage, applicable uniquement si les données sont prises parmi un petit ensemble connu à l'avance). Si l'on ne précise rien, on entend habituellement par algorithme de tri un algorithme général de tri par comparaison.
Les principales caractéristiques qui permettent de différencier les algorithmes de tri sont : la complexité algorithmique, les ressources nécessaires (notamment en terme d'espace mémoire utilisé) et le caractère stable.


Exemples d'algorithmes de tri


Tri à bulles : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, stable et en place ;
Tri par sélection : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, qui trie sur place ;
Tri par insertion : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, stable et en place. C'est le plus rapide et le plus utilisé pour un petit nombre de valeurs à trier ;
Tri rapide (quick sort) : O(nlogn) en moyenne, mais quadratique au pire cas, en place mais pas stable
Tri fusion (merge sort) : O(nlogn) en moyenne et dans le pire des cas, stable mais pas en place ;
Tri par tas (heap sort) : toujours environ deux fois plus lent que le tri rapide, c'est-à-dire aux alentours de O(nlogn), il est donc intéressant de l'utiliser si l'on soupçonne que les données à trier seront souvent des cas quadratiques pour le tri rapide ;
Tri de Shell (shell sort) : Variante du tri par insertion, T(n) = O(n2) en moyenne.


Dernière édition par le Jeu 30 Aoû - 18:01, édité 1 fois
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: Algorithme de tri   Ven 9 Fév - 22:32

excellent travail cher Mohamed

Very Happy:D:D
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: Algorithme de tri   Ven 9 Fév - 22:35

on attend l'explication détaillée et les alghorithmes des autres types de tri
mais je voulais signaler que ce que t'as écrit à propos des tris est valable pour tout autre language de programmation

Very Happy:D:D
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Re: Algorithme de tri   Sam 10 Fév - 13:26

chakerbh a écrit:
on attend l'explication détaillée et les alghorithmes des autres types de tri
mais je voulais signaler que ce que t'as écrit à propos des tris est valable pour tout autre language de programmation

Very Happy:D:D




pas de quoi mon ami, c vrai chaker par exemple on utilise l'algorithme de tri à bulles sur C comme la suite:

Citation :
Une mise en œuvre simple du tri à bulle sur un tableau d'entiers en C :
typedef int tab_entiers[MAX];

void tri_a_bulle(tab_entiers t)
{
int i = 0; /* Indice de répétition du tri */
int j = 0; /* Variable de boucle */
int tmp = 0; /* Variable de stockage temporaire */

/* Booléen marquant l'arrêt du tri si le tableau est ordonné */
bool en_desordre = true;

/* Boucle de répétition du tri et le test qui
arrête le tri dès que le tableau est ordonné */
for(i = 0 ; (i < MAX) && en_desordre; i++)
{
/* Supposons le tableau ordonné */
en_desordre = false;

/* Vérification des éléments des places j et j-1 */
for(j = 1 ; j < MAX - i ; j++)
{
/* Si les 2 éléments sont mal triés */
if(t[j] < t[j-1])
{
/* Inversion des 2 éléments */
tmp = t[j-1];
t[j-1] = t[j];
t[j] = tmp;

/* Le tableau n'est toujours pas trié */
en_desordre = true;
}
}
}
}
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
benha21
utilisateur professionnel
utilisateur professionnel
avatar

Nombre de messages : 349
Age : 31
Date d'inscription : 28/01/2007

MessageSujet: Re: Algorithme de tri   Dim 11 Fév - 15:39

mtcs a écrit:

/* Booléen marquant l'arrêt du tri si le tableau est ordonné */
bool en_desordre = true;

Je rappelle juste que le type bool n'existe pas en C89.



Luc Litzler - L'essentiel du langage C a écrit:
La valeur entière 0 correspond à faux et toute autre valeur différente de zéro à vrai.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://benha21.skyblog.com
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Re: Algorithme de tri   Dim 11 Fév - 16:47

merci benha21
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
benha21
utilisateur professionnel
utilisateur professionnel
avatar

Nombre de messages : 349
Age : 31
Date d'inscription : 28/01/2007

MessageSujet: Re: Algorithme de tri   Dim 11 Fév - 16:55

C'est tout à fait naturel mtcs.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://benha21.skyblog.com
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: Algorithme de tri   Lun 12 Fév - 0:11

benha21 a écrit:
mtcs a écrit:

/* Booléen marquant l'arrêt du tri si le tableau est ordonné */
bool en_desordre = true;

Je rappelle juste que le type bool n'existe pas en C89.



Luc Litzler - L'essentiel du langage C a écrit:
La valeur entière 0 correspond à faux et toute autre valeur différente de zéro à vrai.

merci pour la précition coz Very Happy
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
benha21
utilisateur professionnel
utilisateur professionnel
avatar

Nombre de messages : 349
Age : 31
Date d'inscription : 28/01/2007

MessageSujet: Re: Algorithme de tri   Lun 12 Fév - 0:13

De rien Chak.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://benha21.skyblog.com
Contenu sponsorisé




MessageSujet: Re: Algorithme de tri   

Revenir en haut Aller en bas
 
Algorithme de tri
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum programmation :: Programmation :: Delphi & Pascal :: Pascal :: Cours-
Sauter vers: