Implémentation d'algorithmes classiques/Algorithmes de tri/Tri de Shell
PROCEDURE Tri_Shell(N As Int, ByRef E() As Int)
Local Int D, LIMITE, INTERVERSION, J, I
D = Div(N, 2) ' D = Distance de comparaison
Do ' BOUCLE PRINCIPALE DE SUBDIVISION DES DISTANCES
LIMITE = Sub(N, D) ' Limite ou s'arrêtent les comparaisons
Do ' BOUCLE SECONDAIRE DE RECOMPARAISON EN CAS D'INTERVESION
INTERVERSION = 0 ' A priori pas d'interversion (=0)
J = D ' J%=numéro du 2ème élément dans les comparaisons
For I = 1 To LIMITE% ' BOUCLE de tri avec I%=1er élément de comparaison
Inc J ' J% suis I% en gardant la distance D%
If E(I) > E(J) ' Si il y a lieu d'intervertir
INTERVERSION = I ' On mémorise l"emplacement de l'interversion
Swap E(I), E(J) ' On interverti les 2 éléments
EndIf
Next I%
LIMITE = INTERVERSION ' Prochaine Boucle de tri s'arrêtera à la dernière interversion
Loop While INTERVERSION > 0 ' On refait des comparaisons si l'ordre des éléments a changé
Div D, 2 ' Sinon on divise la distance par 2 et on recommence
Loop While D > 0 ' sauf si plus possible de diminuer la distance
Return
/*
* Exécute un tri par insertion avec la séparation donnée
* If gap == 1, on fait un tri ordinaire.
* If gap >= length, on ne fait rien.
*/
void shellSortPhase(int a[], int length, int gap) {
int i;
for (i = gap; i < length; ++i) {
int value = a[i];
int j;
for (j = i - gap; j >= 0 && a[j] > value; j -= gap) {
a[j + gap] = a[j];
}
a[j + gap] = value;
}
}
void shellSort(int a[], size_t length) {
/*
* gaps[] doit approximer une Série géométrique.
* La sequence suivante est la meilleure connue en terme
* de nombre moyen de comparaisons. voir:
* http://www.research.att.com/~njas/sequences/A102549
*/
static const int gaps[] = {
1, 4, 10, 23, 57, 132, 301, 701
};
int sizeIndex;
for (sizeIndex = sizeof(gaps)/sizeof(gaps[0]) - 1;
sizeIndex >= 0;
--sizeIndex)
shellSortPhase(a, length, gaps[sizeIndex]);
}
/* Réadaptation du code précédent en C++, avec template pour pouvoir s'adapter
à tout type de donnée pour lequel les opérateur '==', '<' et '>' sont définis. */
template<typename T> void SHELLSRT_phase(T* a, unsigned int size, unsigned int gap)
{
for (int i = gap; i < (int)size; ++i)
{
T value = a[i];
int tmp = i - gap;
int j = 0;
for(j = tmp; ((j >= 0) && (a[j] > value)); j -= gap)
a[j + gap] = a[j];
a[j + gap] = value;
}
}
template<typename T> void SHELLSRT_make(T* a, unsigned int size)
{
static const unsigned int gaps[9] = {1, 4, 10, 23, 57, 132, 301, 701, 1750};
unsigned int tmp = 9 -1;
for(unsigned int i = tmp; i != -1; --i)
SHELLSRT_phase(a, size, gaps[i]);
}
using System;
public class ShellSorter
{
public void Sort(int [] list)
{
int inc;
for(inc=1;inc<=list.Length/9;inc=3*inc+1);
for(;inc>0;inc/=3)
{
for(int i=inc+1;i<=list.Length;i+=inc)
{
int t=list[i-1];
int j=i;
while((j>inc)&&(list[j-inc-1]>t))
{
list[j-1]=list[j-inc-1];
j-=inc;
}
list[j-1]=t;
}
}
}
}
public class MainClass
{
public static void Main()
{
int[] iArrary=new int[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47};
ShellSorter sh=new ShellSorter();
sh.Sort(iArrary);
for(int m=0;m<=13;m++)
Console.WriteLine("{0}",iArrary[m]);
}
}
public static void triDeShell(int [] tab,int tailleLogique)
{
int pas = 1;
while( pas < tailleLogique/9)
{
pas = pas*3 + 1; // on fixe le premier pas
}
while (pas > 0) // boucle sur les différents pas
{
for(int série = 0; série <= pas-1; série ++) // boucle sur les séries
{
int positionEltAInsérer = série + pas; // tri par insertion
while(positionEltAInsérer < tailleLogique)
{
int élémentAInsérer = tab[positionEltAInsérer];
int posElemComparé = positionEltAInsérer - pas;
while ((posElemComparé >= 0) && (élémentAInsérer < tab[posElemComparé]))
{
tab[posElemComparé + pas] = tab[posElemComparé];
posElemComparé -= pas;
}
tab [posElemComparé + pas] = élémentAInsérer;
positionEltAInsérer += pas;
}
}
pas = pas/3;
}
}
Implémention du tri Shell en Pascal (par ordre croissant).
type
arrayOfInteger = array of integer;
procedure TriShell(n : integer ; t : arrayOfInteger);
var
p, k, i, j : integer;
begin
(* Recherche du Gap optimal qui est le résultat de *)
(* la suite récurrente : Un = 3.Un-1 + 1 *)
(* Tel que Un < n (Nombre d'éléments du tableau) *)
p := 0;
while (p < n) do p := 3 * p + 1;
while (p <> 1) do
begin
(* On affine peu à peu le Gap *)
(* Gap = 1 ==> Tri par Insertion ordinaire *)
p := p div 3;
for i := p to n-1 do
begin
k := t[i]; (* Valeur à insérer *)
(* Recherche de la position d'insertion *)
j:= i;
while (j >= p ) and (t[j - p] > k) do
begin
t[j] := t[j - p];
j := j - p;
end;
(* Insertion de la valeur à son emplacement *)
t[j] := k;
end;
end;
end;
Python
modifierImplémentation du tri Shell en Python (par ordre croissant).
def triInsertion(tab, i0=0, dec=1):
"""
Trie un tableau à l'aide de l'algorithme de tri par insertion...
Par défaut, trie l'ensemble du tableau.
Si i0 et dec sont spécifiés, trie les cases d'indices i0, i0 + dec, i0 + 2dec, i0 + 3dec...
- Paramètre tab : tableau à trier,
- Paramètre i0 : indice de la première case à trier
- Paramètre dec : décalage entre deux cases à trier
- Ne renvoie rien (modifie le tableau en place)
"""
for i in range(i0 + dec, len(tab), dec):
tempo = tab[i]
j = i # indice de la case libre
while j > i0 and tab[j-dec] > tempo:
tab[j] = tab[j-dec]
j = j - dec
tab[j] = tempo
from math import log, floor
def triShell(tab):
"""
Trie un tableau à l'aide de l'algorithme de tri de Shell
- Paramètre tab : tableau à trier
- Ne renvoie rien.
"""
for k in range(floor(log(len(tab), 2)), 0, -1):
dec = 2**k - 1
for i in range(0, dec):
triInsertion(tab, i, dec)
Implémention du tri Shell en Ruby.
module ShellSort
def self.sort(keys)
sort!(keys.clone)
end
def self.sort!(keys)
gap = keys.size/2
while gap > 0
for j in gap...keys.size
key = keys[j]
i = j
while (i >= gap and keys[i-gap] > key)
keys[i] = keys[i-gap]
i -= gap
end
keys[i] = key
end
gap /= 2
end
keys
end
end
Tout ou partie de cette page est issue de l'article Wikipédia « Tri de Shell » dans sa version du 2 juillet 2010.