Algorithme de tri

Fermé
ammouna - 15 juil. 2008 à 16:48
 sihame - 14 déc. 2010 à 15:10
Bonjour,
je veux savoir l'ordre de complexité des différents algorithmes de tri et surtout celle de lalgorithme de tri par insertion et parsélection!
merci d'avance

4 réponses

bonjour a propos tri par selection j vé te donner une solution voila=
procedure trier (var t:tab;n:integer);
var c,m:integer;
begin
for i:=1 to n-1 do
begin
m:=masc (t,c,n);
if(m<>c) then permuter(c,m,t);
end;
end;

a propos de tri par insertion jé un programme pret pour toi voila=
program triage;
uses wincrt;
type tab = array [1..100] of integer;

procedure saisir (var n:integer );
begin
writeln('donner la dimensin du tableau');
readln(n);
end;

procedure remplir (var t:tab; n:integer);
var i:integer;
begin
for i:=1 to n do
readln(t[i]);
end;

procedure decaler (var t:tab;ind: integer; var p:integer);
var aux,i:integer;
sup:boolean;
begin
aux:=t[ind+1];
i:= ind;
sup:=true;
while ((i>=1) and (sup= true)) do
begin
if (t[i]>aux) then
begin
t[i+1]:=t[i];
i:=i-1;
end
else sup:= false;
end;
p:=i+1;
end;

procedure trie (var t:tab; n: integer);
var c,tmp,ind,p:integer;
begin
for c:= 2 to n do
begin
tmp:= t[c];
decaler (t,c-1,p);
t[p]:=tmp;
end;
end;

procedure afficher (var t:tab; n: integer);
var i: integer;
begin
for i:=1 to n do
writeln (t[i]);
end;

var i,aux,n,ind,p,c:integer;
t:tab;
sup: boolean;
begin
saisir(n);
remplir(t,n);
trie(t,n);
afficher(t,n);
end.

tu peut l'utiliser si tu veut et bon chance ammouna by
4
Salut!
Merci beaucoup ramrouma pour l'aide que tu ma donné pour les programmes de tri!
bon courage à toi!
0
please in the oyher once give us a determinative program pascal
0
lalilu Messages postés 35 Date d'inscription mardi 15 avril 2008 Statut Membre Dernière intervention 17 décembre 2009 1
15 juil. 2008 à 17:00
salut,
tri par insertion
sélection
insertion dichotomique
par bulles --> les 4 ont une complexité de On²
cependant, le tri par bulles est plus lent que les autres et le tri par insertion dichotomique est plus rapide (bien que pour les 4 on reste dans le même ordre de grandeur.

tri rapide (quick sort) --> complexité = nlog(n) donc beaucoup plus rapide.

ce sont les seuls algos que je connaisse
bon courage
1
salut
merci beaucoup pour votre aide!
0
KX Messages postés 16668 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 17 mars 2023 3 004
15 juil. 2008 à 17:14
D'un point de vue efficacité, on ne peut pas faire mieux qu'un tri avec une complexité en O(n.log n)

Le tri par fusion permet, d'atteindre cette efficacité dans tout les cas, mais il utilise plus de mémoire que les autres tris (ce qui en soit n'est presque plus un problème)

Par contre j'ai entendu dire que la complexité en O( n.log n ) du quick sort, était une "publicité mensongère" car selon les cas sa complexité atteindrait O( n² )
1
haydens Messages postés 81 Date d'inscription mercredi 29 août 2007 Statut Membre Dernière intervention 20 mai 2018 5
20 nov. 2008 à 23:24
En effet le trie rapide peut etre en n² dans le pire des cas (malheuresement ce pire des cas arrive) souvent, donc on prend notre liste on "fou le bordel" et la c'est efficace en gros.
"foutre le bordel" prend n calcule donc on reste en lon au final

plus d'information sur : https://fr.wikipedia.org/wiki/Tri_rapide
0