Discussion :

[phplive]

Bsr

Après avoir constater avec horreur que QuickSort n'était pas "stable" j'ai donc implémenté l'algoritme MergeSort afin de trier des TList

MergeSort semble assez rapide (sur 100000 items) mais par contre il demande de la mémoire (la moitié de celle utilisée par la liste à trier en fait)

Est-il vraiment plus lent que Quicksort ?


C'est juste pour info

Merci

@+
Php

[portu]

Il faudrait peut être poser cette question dans le forum algo.

[e-ric]

Salut

Je voudrais être sûr de ce que tu entends par stabilité.
Il s'agit de la propriété d'algorithme de tri ou d'un mauvais fonctionnement du tri ?

S'il s'agit de la propriété en terme d'algorithme de tri, ne peux-tu pas aménager la fonction de comparaison de façon à conserver cette stabilité ?


cdlt

e-ric

[phplive]

Bjr E-ric

Oui par stabilité j'entends le fait que l'algorithme Quicksort ne respecte pas l'ordre initial des éléments qui n'ont pas besoin d'être permuttés.
Pas que l'algo plante bien sûr !

Par ex si tu considères une liste de personne triée par Prénom+Nom et que tu la retries avec Quicksort uniquement sur le Prénom rien ne garantie que pour un même Prénom, les Noms seront toujours classés par ordre croissant : avec MergeSort si !

Voilà

@+
Php

[e-ric]

Si le volume de données n'est pas trop important, le tri par sélection peut être suffisant.

cdlt

e-ric

[phplive]

Oui effectivement

Enfin maintenant que ma procédure de tri est écrite je vais l'utiliser

Pour ceux que ce intéressent voici le code

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
type
  // Doit retourner 
  // -1 si Obj1 < Obj2 (ou une propriété de l'objet)
  // 0  si Obj1 = Obj2
  // +1 si Obj1 > Obj2
  TItemCompare = function (Obj1, Obj2: TObject): Integer;
 
 
 
procedure MergeSort(AList : TList; AComparator: TItemCompare);
var
  TempList : PPointerList;
  SortedList : PPointerList;
 
  procedure Merge(MinIndex,Middle,MaxIndex : Integer);
  var
    i,j,k : Integer;
  begin
 
     // Copie la moitié de la liste dans une liste temporaire
     System.Move(SortedList^[MinIndex], TempList^[0],
        (Middle - MinIndex+1) * SizeOf(Pointer));
 
     i := 0;
     j := Middle+1;
     k := MinIndex;
     // copy back next-greatest element at each time
     while (k<j) and (j<=MaxIndex) do
     begin
        if AComparator(TObject(TempList^[i]),TObject(SortedList^[j])) <= 0 then
        begin
          SortedList^[k] := TempList^[i];
          Inc(i);
        end
        else
        begin
          SortedList^[k] := SortedList^[j];
          Inc(j);
        end;
        Inc(k);
     end;
 
     // copy back remaining elements of first half (if any)
     while (k<j) do
     begin
       SortedList^[k] := TempList^[i];
       Inc(k);
       Inc(i);
     end;
  end;
 
 
  procedure MergeDivide(MinIndex,MaxIndex : Integer);
  var
    Middle : Integer;
  begin
    if (MinIndex < MaxIndex) then
    begin
      Middle := (MaxIndex+MinIndex) shr 1;
      MergeDivide(MinIndex, Middle);
      MergeDivide(Middle+1, MaxIndex);
      Merge(MinIndex, Middle, MaxIndex);
    end;
  end;
 
begin
  SortedList :=  AList.FList.List;
  // Alloue un espace mémoire suffisant pour stocker la moitié des éléments
  // de la liste
  GetMem(TempList,SizeOf(Pointer)*((AList.Count shr 1)+1));
  MergeDivide(0,AList.Count-1);
  FreeMem(TempList);
end;

Si vous trouver une erreur merci de me la signaler SVP

@+
Php