Algorythmes de tri

Soyez le premier à donner votre avis sur cette source.

Vue 9 340 fois - Téléchargée 458 fois

Description

Un petit code qui va vous permettre de comparer le comportement de différents algorythmes de tri.

Source / Exemple :


unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Button2: TButton;
    Button3: TButton;
    Button4: TButton;
    Ausgabe: TEdit;
    Vergleiche_ausgabe: TEdit;
    Vertausch_Ausgabe: TEdit;
    Label1: TLabel;
    Label2: TLabel;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
    procedure Button4Click(Sender: TObject);
  private
    { Déclarations privées }
  public
    { Déclarations publiques }
  end;

var
  Form1: TForm1;
  Wort:string;
  Vertauschung,Vergleiche:integer;
implementation

{$R *.DFM}

Procedure SelSort(var Wort:String);
var i,j,N,min:integer;
    t:Char;
    Begin
    N:=length(Wort);
    for i:=1 to N do
        Begin
        min:=i;
        for j:=i+1 to N do begin inc(Vergleiche);
            if Wort[j]<Wort[min] then begin min:=j end;
            end;
        t:=Wort[min];Wort[min]:=Wort[i];Wort[i]:=t;
        inc(Vertauschung,3);
        end;
    end;

Procedure InsertSort(var Wort:String);
var i,j,N:integer;
    t:Char;
    Begin
    N:=Length(Wort);
    for i:=2 to N do
        begin
        t:=Wort[i];
        inc(Vertauschung);
        j:=i;
        While t<Wort[j-1] do
              begin
              Wort[j]:=Wort[j-1];
              inc(Vertauschung);
              j:=j-1;
              end;
        inc(Vergleiche,i+1-j);
        Wort[j]:=t;
        inc(Vertauschung);
        end;
    end;

Procedure BubbleSort(var Wort:String);
var i,j,N:integer;
    t:Char;
    Begin
    N:=Length(Wort);
    for i:=N downto 1 do
        for j:=2 to i do begin
            inc(Vergleiche);
            if Wort[j]<Wort[j-1] then
               begin
               t:=Wort[j];
               Wort[j]:=Wort[j-1];
               Wort[j-1]:=t;
               inc(Vertauschung,3);
               end;
            end;
    end;

Procedure QuickSort(l,r:integer);
var i:integer;
    function Partition(l,r:integer):integer;
    var i,j:integer;
        t:Char;
        begin
        j:=r;
        i:=l-1;
        repeat
        repeat i:=i+1 ; inc(Vergleiche); until Wort[i]>=Wort[r];
        repeat j:=j-1 ; inc(Vergleiche); until Wort[j]<=Wort[r];
        t:=Wort[i];Wort[i]:=Wort[j];Wort[j]:=t;
        inc(Vertauschung,3);
        until j<=i;
        Wort[j]:=Wort[i];Wort[i]:=Wort[r];Wort[r]:=t;
        inc(Vertauschung,3);
        Partition:=i;
        end;

    begin
    if r>l then
    begin
    i:=Partition(l,r);
    quicksort(l,i-1);
    quicksort(i+1,r);
    end;
    end;

procedure TForm1.Button1Click(Sender: TObject);
begin
Wort:=Ausgabe.text;
Vertauschung:=0;
Vergleiche:=0;
//Wort:=' '+Wort;
SelSort(Wort);
Ausgabe.text:=Wort;
Vergleiche_ausgabe.Text:=IntToStr(Vergleiche);
Vertausch_Ausgabe.Text:=IntToStr(Vertauschung);
end;

procedure TForm1.Button2Click(Sender: TObject);
begin
Wort:=Ausgabe.text;
Vertauschung:=0;
Vergleiche:=0;
//Wort:=' '+Wort;
InsertSort(Wort);
Ausgabe.text:=Wort;
Vergleiche_ausgabe.Text:=IntToStr(Vergleiche);
Vertausch_Ausgabe.Text:=IntToStr(Vertauschung);
end;

procedure TForm1.Button3Click(Sender: TObject);
begin
Wort:=Ausgabe.text;
Vertauschung:=0;
Vergleiche:=0;
//Wort:=' '+Wort;
BubbleSort(Wort);
Ausgabe.text:=Wort;
Vergleiche_ausgabe.Text:=IntToStr(Vergleiche);
Vertausch_Ausgabe.Text:=IntToStr(Vertauschung);
end;

procedure TForm1.Button4Click(Sender: TObject);
begin
Wort:=Ausgabe.text;
Vertauschung:=0;
Vergleiche:=0;
//Wort:=' '+Wort;
QuickSort(1,length(Wort));
Ausgabe.text:=Wort;
//Ausgabe.text:=Copy(Wort,2,Length(Wort)-1);
Vergleiche_ausgabe.Text:=IntToStr(Vergleiche);
Vertausch_Ausgabe.Text:=IntToStr(Vertauschung);
end;

end.

Conclusion :


si vous avez des questions...

Codes Sources

A voir également

Ajouter un commentaire Commentaire
Messages postés
4
Date d'inscription
mardi 20 avril 2004
Statut
Membre
Dernière intervention
16 juillet 2008

Bon travail, néanmoins il manque un des principaux tri, à savoir le HeapSort, en O(n.Log n)

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.