Algorithme de tri

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
Configuration: Windows Vista
Internet Explorer 7.0

4 réponses

  1. 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
    1. Salut!
      Merci beaucoup ramrouma pour l'aide que tu ma donné pour les programmes de tri!
      bon courage à toi!
    2. please in the oyher once give us a determinative program pascal
  2. 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!
  3. Modérateur
    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. 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