ALGORITHME DE TRI
Il existe de nombreux algorithmes de tri, je tenterais seulement de vous montrer les plus populaires et les plus utilisés.Il n'y a pas vraiment de tri qui soit meilleur que les autres, la vitesse d'exécution d'un algorithme dépend des donnés à trier. Certains algorithmes sont plus efficaces dans certaines circonstances c'est ce que nous tenterons de vous montrer
Complexité
Dans le but de mesurer la complexité d'un algorithme de tri,deux quantités sont à observer :- le nombre d'échanges effectués,
- le nombre de comparaisons effectués entre éléments du tableau.
Grand O
Le grand O est utilisé pour indiquer la croissance d'une fonction. Le symbole utilisé est O.Grand oméga
Le grand oméga est utilisé pour avoir la limite inférieur d'une fonction, en d'autre mot le minimum. Le symbole utilisé est ΩLes tries
Buble sort
Ce type de tri est le plus simple, mais souvent le moins efficace. Il peut s'avérer utile pour des petits tris étant donné sa simplicité, il y a peu de chance de faire des erreurs.L'idée du buble sort est de comparer un élément à son voisin et de les permuter si l'élément est plus grand que celui-ci.
procedure BubbleSort(var tabNote: array of Integer); var i,j: integer; temp: integer; begin for i := high(tabNote) downto low(tabNote) do for j := low(tabNote) to high(tabNote)-1 do if tabNote[j] >tabNote[j + 1] then begin temp := tabNote[j]; tabNote[j] := tabNote[j + 1]; tabNote[j + 1] := temp; end; end;
Comme vous pouvez le voir un tel algorithme est lent, imaginez trier 1000 000 de donnés avec ça. Vous pouvez remarquer que lorsqu'on change de position l'élément, il arrive souvent que le tableau soit trié avant que l'algorithme soit fini. On peut aisément améliorer cela en ajoutant une petite vérification.
procedure BubbleSort(var tabNote: array of Integer); var i,j: integer; temp: integer; Test: Boolean; begin for i := low(tabNote) to high(tabNote) do begin Test := false; for j := low(tabNote) to high(tabNote) - 1 do begin if tabNote[j] > tabNote[Succ(j)] then begin temp := tabNote[j]; tabNote[j] := tabNote[Succ(j)]; tabNote[Succ(j)] := temp; Test := true; end; end; if not Test then break; end; end;
Complexité
La complexité est O(n^2) pour des données mélangées, mais l'approche est O(n) si la liste est presque trié au début.Insertionsort
Cette méthode est semblable à celle que nous utilisons lorsqu'on trie des cartes. Nous prenons chaque nouvelle carte et nous l'insérons à la bonne position dans le paquet déjà trié. Ce tri est particulièrement rapide lorsqu'il y a peu de désordre.procedure Insertionsort(var tabNote: array of Integer); var i, j: Integer; temp: Byte; begin tabNote[0] := 0; //garde l'algo hors de l'alignement for i := 2 to high(tabNote) do begin //débute à 2 puisque le premier élément //n'est ni plus petit //ni plus grand que lui-même temp := tabNote[i] ; j := i; while tabNote[Pred(j)] > temp do begin tabNote[j] := tabNote[Pred(j)]; dec(j); end; tabNote[j] := temp; //insère l'élément à la position trouvé end; end;
Complexité
Le meilleur cas est n et le pire cas est O(n2)Shellsort
Ce tri est similaire à l'insertionsort. Il est un peu plus performant. L'insertionsort n'est pas très rapide puisque les éléments sont bougés d'un espace à la fois. Nous pouvons le faire bouger de plusieurs espaces, jusqu'à ce que nous trouvions le bon emplacement. Pour arriver à une telle solution, nous pouvons réduire la grosseur de k, chaque fois que nous constatons que (j-k) ième élément est plus grand que l'élément actuel. Nous pouvons diviser k par 3 chaque fois.procedure ShellSort(var A : ArrayType; N : integer); var Done : boolean; Jump,I,J : integer; begin Jump := N; while (Jump > 1) do begin Jump := Jump div 2; repeat Done := true; for J := 1 to (N - Jump) do begin I := J + Jump; if (A[J] > A[I]) then begin Swap(A[J], A[I]); Done := false end; end; until Done; end end;
Quicksort
Quicksort est l'algorithme de tri le plus populaire. Sur une entré aléatoire, Quicksort est le plus rapide des algorithmes que je connais. Quicksort est implanté de façon récursif, il peut ainsi être plus complexe à comprendre.1. On doit spécifier un élément x pour établir l'alignement.
2. Chaque élément plus petit que x sera mis à droite et ceux plus grand à gauche.
3. Quicksort s'appelle et passe les deux parties. Lorsqu'il est appelé avec un tableau de grosseur 1, un élément a été trié.
4. Lorsque quicksort revient de la récursion, les deux parties ont été triées et peuvent être mises ensemble.
procedure Quicksort(var tabNote: TArray,longueur, r: Integer); var i, j: Integer; temp, old: Byte; begin old := tabNote[(longueur + r) div 2]; i := longeur; j := r; repeat while tabNote[i] < old do inc(i); while old < tabNote[j] do dec(j); if i <= j then begin temp := tabNote[i]; tabNote[i] := tabNote[j]; tabNote[j] := temp; inc(i); dec(j); end; until i > j; if longeur < j then Quicksort( longueur, j); if i < r then Quicksort( i, r); end;
Complexité
Le pire cas est O(n2).La moyenne des résultats : O(n log n)..
Selection Sort
Ce tri parcourt le tableau à trier, cherche l'élément à remplacer et le permute. Ce tri peut s'avérer intéressant, s'il y a peu d'affectation (fichier).procedure SelectionSort(var tabNote: array of Integer); var I, J, temp: Integer; begin for I := Low(tabNote) to High(tabNote) - 1 do for J := High(tabNote) downto I + 1 do if tabNote[I] > tabNote[J] then begin temp := tabNote[I]; tabNote[I] := tabNote[J]; tabNote[J] := temp; end; end;
Complexité
La moyenne des résultats :O( n^2).Un programme utilisant de nombreux algorithmes de tri est disponible ici.
Aucun commentaire:
Enregistrer un commentaire