Smoothsort - Définition
La liste des auteurs de cet article est disponible ici.
Introduction
Smoothsort est un algorithme de tri par comparaison inventé en 1981 par Edsger Dijkstra. C'est un tri de complexité en O(n.logn), tout comme le tri par tas dont il est inspiré, et le tri rapide dans la plupart des cas. Mais si les données sont déjà presque triées, il est de complexité en O(n). Ce tri est alors plus rapide que le tri rapide.
La transition entre les temps d'exécution entre les listes déjà triées et les listes mélangées ou à l'envers est progressive d'où le nom Smoothsort, smooth signifiant doux, lisse. C'est un tri sur place, c'est-à-dire qu'il n'y a pas de zone mémoire allouée supplémentaire pour stocker les éléments.
Si l'algorithme Smoothsort est plus rapide que le tri par tas pour des listes peu mélangées, il est légèrement plus lent que le tri par tas pour des listes qui sont plutôt dans le sens décroissant au départ. En effet, les données de départ sont alors plus proche de la structure de tas.
But de Smoothsort
Le tri par tas a un inconvénient majeur, c'est que si les données sont déjà triées, elles vont être d'abord mélangées avant d'être de nouveau triées. Cela est dû au fait que les données intermédiaires sont un arbre binaire où les noeuds parents sont supérieurs aux noeuds enfants, les parents étant sur la gauche des enfants dans le tableau.
Ainsi, lors de cette phase du tri par tas, les premiers éléments du tableau sont les plus grands, alors qu'à la fin du tri, les plus grands éléments doivent être à la fin du tableau (on suppose qu'on trie par ordre croissant).
Pour pallier cet inconvénient, Smoothsort utilise un arbre binaire dans l'autre sens, c'est-à-dire dont l'ordre partiel imposé aux noeuds de l'arbre soit dans le même sens que l'ordre final voulu (les données de l'arbre et les données d'entrées sont stockées dans le même tableau, comme pour le tri par tas). Cela demande une réorganisation des données de l'arbre au fur et à mesure du tri. Mais comme l'arbre est construit dans le sens croissant, si le tableau est déjà trié, il n'y a rien à faire et les données ne sont pas mélangées.
Implémentation en Delphi
unit USmoothsort; { Delphi implementation of Dijkstra's algorithm } interface type TItem = Double; { data type } function IsAscending(v1,v2: TItem): boolean; { comparison function } { sorting function } procedure SmoothSort(var A: array of TItem); implementation { customizable comparison function } function IsAscending(v1,v2: TItem): boolean; begin result := v1<=v2; end; { implementation of Djikstra's algorithm } procedure SmoothSort(var A: array of TItem); var q,r, p,b,c, r1,b1,c1, N: integer; procedure up(var vb,vc: integer); var temp: integer; begin temp := vb; vb := vb+vc+1; vc := temp; end; procedure down(var vb,vc: integer); var temp: integer; begin temp := vc; vc := vb-vc-1; vb := temp; end; procedure sift; var r0, r2: integer; T: TItem; begin r0 := r1; T := A[r0]; while b1>=3 do begin r2 := r1-b1+c1; if not IsAscending(A[r1-1],A[r2]) then begin r2 := r1-1; down(b1,c1); end; if IsAscending(A[r2],T) then b1 := 1 else begin A[r1] := A[r2]; r1 := r2; down(b1,c1); end; end; if r1<>r0 then A[r1] := T; end; procedure trinkle; var p1,r2,r3, r0 : integer; T: TItem; begin p1 := p; b1 := b; c1 := c; r0 := r1; T := A[r0]; while p1>0 do begin while (p1 and 1)=0 do begin p1 := p1 shr 1; up(b1,c1); end; r3 := r1-b1; if (p1=1) or IsAscending(A[r3],T) then p1 := 0 else {p1>1} begin p1 := p1 - 1; if b1=1 then begin A[r1] := A[r3]; r1 := r3; end else if b1>=3 then begin r2 := r1-b1+c1; if not IsAscending(A[r1-1],A[r2]) then begin r2 := r1-1; down(b1,c1); p1 := p1 shl 1; end; if IsAscending(A[r2],A[r3]) then begin A[r1] := A[r3]; r1 := r3; end else begin A[r1] := A[r2]; r1 := r2; down(b1,c1); p1 := 0; end; end;{if b1>=3} end;{if p1>1} end;{while} if r0<>r1 then A[r1] := T; sift; end; procedure semitrinkle; var T: TItem; begin r1 := r-c; if not IsAscending(A[r1],A[r]) then begin T := A[r]; A[r] := A[r1]; A[r1] := T; trinkle; end; end; begin N := length(A); q := 1; r := 0; p := 1; b := 1; c := 1; //building tree while q < N do begin r1 := r; if (p and 7) = 3 then begin b1 := b; c1 := c; sift; p := (p+1) shr 2; up(b,c); up(b,c); end else if (p and 3) = 1 then begin if q + c < N then begin b1 := b; c1 := c; sift; end else trinkle; down(b,c); p := p shl 1; while b > 1 do begin down(b,c); p := p shl 1; end; p := p+1; end; q := q + 1; r := r + 1; end; r1 := r; trinkle; //bulding sorted array while q>1 do begin q := q - 1; if b = 1 then begin r := r - 1; p := p - 1; while (p and 1) = 0 do begin p := p shr 1; up(b,c); end; end else if b >= 3 then begin p := p - 1; r := r-b+c; if p > 0 then semitrinkle; down(b,c); p := p shl 1 + 1; r := r+c; semitrinkle; down(b,c); p := p shl 1 + 1; end; //element q is done end; //element 0 is done end; end.
