Implémentation d'algorithmes classiques/Algorithmes de tri/Smoothsort
Delphi
[modifier | modifier le wikicode]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#
[modifier | modifier le wikicode]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.