Smoothsort

Un article de Wikipédia, l'encyclopédie libre.
Ceci est une version archivée de cette page, en date du 2 septembre 2010 à 14:57 et modifiée en dernier par Richardbl (discuter | contributions). Elle peut contenir des erreurs, des inexactitudes ou des contenus vandalisés non présents dans la version actuelle.

Smoothsort est un algorithme de tri par comparaison inventé en 1981 par Edsger Dijkstra. C'est un tri de complexité en , 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 . 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.

Etapes de l'algorithme

La première étape consiste à transformer le tableau en un arbre binaire. Le premier élément est déjà trivialement bien ordonné, puis on ajoute un à un les éléments suivants. On réordonne chaque fois un peu les éléments si nécessaire pour qu'ils correspondent aux critères :

  • Chaque noeud ne peut être supérieur à son noeud parent
  • Le premier noeud enfant ne peut être supérieur au deuxième noeud enfant

NB: Ces critères imposent un ordre dans le même sens que le sens trié, d'où l'intérêt de cet algorithme.

La deuxième étape consiste à retransformer l'arbre binaire en tableau trié. Chaque élément en partant de la droite est laissé tel quel car il s'agit de la racine de l'arbre qui est déjà le plus grand élément, et l'arbre restant est réordonné si nécessaire. On fait ceci jusqu'à arriver à un tableau trié.

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.

Implémentation en C#

Implémentation accompagnée de petits exemple pour l'optimiser en fonction de structure particulière (tri de flottant, pointeur vers un objet...)

using System;
using System.Collections.Generic;
using System.Text;

namespace NitsujMoteur
{
    #region comparaisons
    public struct elem_indicéf
    {
        public float indice;
        public object elem;
        public int indiceOrig;//n'est pas rempli par le code, optionnel si besoin est.
    }

    public class indicef_comparer : IComparer<elem_indicéf>
    {
        #region IComparer<elem_indicéf> Membres

        int IComparer<elem_indicéf>.Compare(elem_indicéf x, elem_indicéf y)
        {
            if (x.indice < y.indice)
                return -1;
            else if (x.indice > y.indice)
                return 1;
            else
                return 0;
            //return x.indice - y.indice;
        }

        #endregion
    }

    public struct elem_indicé
    {
        public int indice;
        public object elem;
        public int indiceOrig;//n'est pas rempli par le code, optionnel si besoin est
    }

    public class indice_comparer : IComparer<elem_indicé>
    {
        #region IComparer<elem_indicé> Membres

        int IComparer<elem_indicé>.Compare(elem_indicé x, elem_indicé y)
        {
            return x.indice - y.indice;
        }

        #endregion
    }

    public class int_comparer : IComparer<int>
    {
        #region IComparer<int> Membres //public car dans l'interface...

        int IComparer<int>.Compare(int x, int y)
        {
            return x - y;
        }

        #endregion
    }
    #endregion

    public class Trie<T, TC> where TC : IComparer<T>
    {
        /*	An algorithm developed by Edsger Dijkstra based on the same principle as
 *	heapsort.  By using a postorder traversal of a heap-like structure, O(n)
 *	time complexity is achieved for already-sorted data.
 *	Time complexity:
 *		O(n log n) worst case
 *		O(n) best case
 *	Working memory:
 *		O(1) all cases
 */
        private static void up(ref int b, ref int c)
        {
            int temp = b + c + 1;
            c = b;
            b = temp;
        }
        private static void down(ref int b, ref int c)
        {
            int temp = b - c - 1;
            b = c;
            c = temp;
        }
        private static void sift(int r, int b, int c, T[] data, TC Comp)
        {
            while (b >= 3)
            {
                int r2 = r - b + c;

                if (Comp.Compare(data[r2], data[r - 1]) < 0)//data[r2] < data[r - 1])
                {
                    r2 = r - 1;
                    down(ref b, ref c);
                }

                if (Comp.Compare(data[r], data[r2]) >= 0)//data[r] >= data[r2])
                {
                    b = 1;
                }
                else
                {
                    swap(ref data[r], ref data[r2]);
                    r = r2;
                    down(ref b, ref c);
                }
            }
        }
        private static void trinkle(int r, int p, int b, int c, T[] data, TC Comp)
        {
            while (p > 0)
            {
                int r3;

                while (p % 2 == 0)
                {
                    p /= 2;
                    up(ref b, ref c);
                }
                r3 = r - b;

                if (p == 1 || Comp.Compare(data[r3], data[r]) <= 0)//data[r3] <= data[r])
                {
                    p = 0;
                }
                else
                {
                    p--;
                    if (b == 1)
                    {
                        swap(ref data[r], ref data[r3]);
                        r = r3;
                    }
                    else if (b >= 3)
                    {
                        int r2 = r - b + c;
                        if (Comp.Compare(data[r2], data[r - 1]) < 0)//data[r2] < data[r - 1])
                        {
                            r2 = r - 1;
                            down(ref b, ref c);
                            p *= 2;
                        }

                        if (Comp.Compare(data[r3], data[r2]) >= 0)//data[r3] >= data[r2])
                        {
                            swap(ref data[r], ref data[r3]);
                            r = r3;
                        }
                        else
                        {
                            swap(ref data[r], ref data[r2]);
                            r = r2;
                            down(ref b, ref c);
                            p = 0;
                        }
                    }
                }
            }
            sift(r, b, c, data, Comp);
        }

        private static void semitrinkle(int r, int p, int b, int c, T[] data, TC Comp)
        {
            int r1 = r - c;
            if (Comp.Compare(data[r1], data[r]) > 0)//data[r1] > data[r])
            {
                swap(ref data[r], ref data[r1]);
                trinkle(r1, p, b, c, data, Comp);
            }
        }

        private static void swap(ref T x, ref T y)
        {
            T temp = x;
            x = y;
            y = temp;
        }

        public static void smoothSort(T[] data, TC Comp)
        {
            if (data.Length <= 1)
                return;
            int q = 1, r = 0, p = 1, b = 1, c = 1;

            while (q != data.Length)
            {
                if (p % 8 == 3)
                {
                    sift(r, b, c, data, Comp);
                    p = (p + 1) / 4;
                    up(ref b, ref c); up(ref b, ref c);
                }
                else if (p % 4 == 1)
                {
                    if (q + c < data.Length)
                    {
                        sift(r, b, c, data, Comp);
                    }
                    else
                    {
                        trinkle(r, p, b, c, data, Comp);
                    }
                    do
                    {
                        down(ref b, ref c);
                        p *= 2;
                    } while (b != 1);
                    p++;
                }
                q++; r++;
            }
            trinkle(r, p, b, c, data, Comp);

            while (q != 1)
            {
                q--;
                if (b == 1)
                {
                    r--; p--;
                    while (p % 2 == 0)
                    {
                        p /= 2;
                        up(ref b, ref c);
                    }
                }
                else if (b >= 3)
                {
                    p--;
                    r += c - b;
                    if (p != 0) semitrinkle(r, p, b, c, data, Comp);
                    down(ref b, ref c);
                    p = 2 * p + 1;
                    r += c;
                    semitrinkle(r, p, b, c, data, Comp);
                    down(ref b, ref c);
                    p = 2 * p + 1;
                }
            }
        }

    }

    #region spécialisation
    public class Trie_elem_indicéf : Trie<elem_indicéf, indicef_comparer>
    {
        public static void smoothSort(elem_indicéf[] data)
        {
            smoothSort(data, new indicef_comparer());
        }
    }
    public class Trie_elem_indicé : Trie<elem_indicé, indice_comparer>
    {
        public static void smoothSort(elem_indicé[] data)
        {
            smoothSort(data, new indice_comparer());
        }
    }
    #endregion
}

Voir aussi

Lien externe

Modèle:Algorithme de tri