Implémentation d'algorithmes classiques/Algorithmes de tri/Smoothsort

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.

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
}

Tout ou partie de cette page est issue de l'article Wikipédia « Smoothsort » dans sa version du 2 septembre 2010.