Upload
fontaine-fafany
View
82
Download
0
Embed Size (px)
Citation preview
République Algérienne Démocratique et Populaire
Ministère de l’Enseignement Supérieur et de la Recherche Scientifique
Université de Ghardaïa
Spécialité : Master I - SIEC
Système Intelligent pour Extraction des Connaissance
PAR :
Soumia Elyakote HERMA
ANNEE UNIVERSITAIRE: 2014/2015
Module : Conception et Analyse des Algorithmes TP N° 02:
Enseignant :
Slimane BELLAOUAR
Expérimentation des séquences
du tri par Shell
Plan Introduction au Tri Shell Principe de l’expérimentation Implémentation de l’algorithme de tri par Shell
◦ Implémentation de tri de Shell (2^k)
◦ Implémentation de tri de Hibbard (2^k-1)
◦ Implémentation de tri de Knuth l (3*k+1)
◦ Implémentation de tri de Sedgewick
Expérimentations sur des données déférentes Exécution sur java Représentation et interprétation des résultats Les graphes correspondants Les Résultats Représentation des résultats des (4) séquences sur des
tableaux avec des entrées tirés, aléatoires puis des entrées trié à l’envers
Conclusion
Le TP expérimente des séquences du
tri de Shell utilisé depuis la séquence
introduit par Shell 1959 arrivant au
l’implémentation supposé par Sedgewick
1956,
Pour remarqué l’impact de chaque
séquence en choisissant les quatre (4)
séquences :
01) Shell : 1, 2, 4, 8, 16, 32,…..
02) Hibbard : 1, 3, 7, 15, 32,…..
03) Knuth : 1, 4, 13, 40, 121,…..
04) Sedgewick : 1, 5, 19, 41, 109, 209,
505, 929,….
Objectif:
Le tri de Shell:
Le tri de Shell utilise un séquence d’entiers,
appelée séquence-h, il effectue chaque entier de cette
séquence un tri par insertion sur les éléments d’indice i,
i+h, i+2h,,,, ’cas séquence Shell original’
partant d’une valeur de h très grande pour arriver à 1,
( qui est le tri par insertion classique)
Principe de l’expérimentation:
On prend le nombre des comparaisons comme opération principale dans les implémentations.
On a posé le compteur du nombre des comparaisons dans la fonction less() pour bien mesuré l’exécution de l’opération principale.
On exécute le code (les implémentations) sur des tailles différentes.
On exécute le code sur des tableaux avec des données triées puis des données aléatoires ensuite des données triées à l’envers.
On utilise un class pour chaque implémentation du séquence.
On utilise les class less() , exch() et is sorted() depuis livre de Algorithmes Pr Robert Sedgewick.
Implémentation de tri de Shell séquence original (2^k) en Java :
/** Shell sort using Shell's (original) gap sequence: n/2, n/4, ..., 1. */
public void shell_2k_Sort(Comparable[] array)
{
compteur_if.compt_if = 0;
int n = array.length;
// ***** sequence 2^k
for (int gap = (int) (Math.pow(2,(Math.log(n)/Math.log(2)))); gap > 0; gap = gap / 2){
for (int i = gap; i < n; i++){
for (int j = i; j > 0 && less(array[j], array[j - 1]); j--)
exch(array, j, j - 1);
}
}
System.out.println(" *shell_2k_1* comparisons operations : "
+ compteur_if.compt_if);
}
Résultats:seq 2^k
Trié aléatoire invers
1000 8010 253224 507509
4000 40012 4071707 8038011
6000 66013 8956931 18063011
8000 88013 16079357 32084012
Les graphes correspondent :
0 1000 2000 3000 4000 5000 6000 7000 8000 90000
5000000
10000000
15000000
20000000
25000000
30000000
35000000
Résultat séquence de Shell (2^k) avec les 3 tableaux
seq 2^k Trié
seq 2^k aléatoire
seq 2^k invers
Taille des données
Nbr
Com
para
isio
n
Analyse : le graphe extraite de l’algorithme du tri Shell , le graphe est quadratique alors La complexités : O(N^2)
L’implémentation et les résultats du séquence de
Hibbard, 1963 est presque comme la séquence de
Shell donc nous avons évité de refaire des
informations, Tel que la différence est dans le segment
de code de la séquence (2^k-1) est ;
for (int gap = (int) (Math.pow (2,(Math.log (n )/Math.log
(2))))-1; gap > 0; gap = gap / 2).
Implémentation de tri de séquence de Hibbard, 1963 (2^k-1) en Java :
Implémentation de tri de Knuth, 1973 (3*k+1) :
public void shellSort(Comparable[] a) {
compteur_if.compt_if = 0;
int N = a.length;
int h = 1;
while (h < N / 3)
h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
while (h >= 1) // h-sort the array {
for (int i = h; i < N; i++) // Insert a[i] among a[i-h], ..
{
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
exch(a, j, j - h);
}
h = h / 3;
}
System.out.println("comparisons operations : " + compteur_if.compt_if);// +" + exchanges operations : "+compt_exch);
}
Résultats
Les graphes correspondent :
seq Knuth
Trié aléatoire invers
1000 5457 12206 85504000 27084 62276 442216000 43084 97839 634348000
59084 139581 93463
0 1000 2000 3000 4000 5000 6000 7000 8000 90000
20000
40000
60000
80000
100000
120000
140000
160000
Résultat sequence de Knuth(3*h+1) avec les 3 tableaux
seq Knuth Trié
seq Knuth aléatoire
seq Knuth invers
Taille des données
Nbr
Com
para
isio
n
Analyse : le graphe extraire de l’algorithme du tri par Knuth, le graphe donne une complexités amélioré : O(N3/2)
Implémentation de tri de Sedgewick 1986 :
public void sedgewick_sort(Comparable[] a) { // Sort a[] into increasing order.
compteur_if.compt_if = 0;
int h = 0;
int N = a.length;
int seq[] = { 1073643521, 268386305, 150958081, 67084289, 37730305,16764929, 9427969, 4188161,2354689, 1045505, 587521, 260609,146305, 64769, 36289, 16001, 8929, 3905, 2161, 929, 505, 209,109, 41, 19, 5, 1 };
int val = 0;
while (seq[val] > N) val++;
h = seq[val];
while (h > 0) {
for (int i = h; i < N; i++) {
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
exch(a, j, j - h);
}
}
val++;
if (seq[val - 1] != 1) h = seq[val];
else h = 0;
}
System.out.println( " *Sedgewick* comparisons operations : "+compteur_if.compt_if); }
Résultats
Les graphes correspondent :
seq Sedgewick
Trié aléatoire invers
1000 6182 11403 90464000 32116 53876 465996000 52116 84773 743058000 72116 114894 101339
0 1000 2000 3000 4000 5000 6000 7000 8000 90000
20000
40000
60000
80000
100000
120000
140000
Résultat séquence de Sedgewick avec les 3 tableaux
seq Sedgewick Trié
seq Sedgewick aléa-toire
seq Sedgewick invers
Taille des données
Nbr
Com
para
isio
n
Analyse : le graphe extraire de l’algorithme du tri par Sedgewick , le graphe donne une complexités optimal : O(N4/3).
Image d’exécution sur java:
tableau représente les résultats de les (4) séquence sur des tableaux triés en plusieurs tailles :
Trié
2^k 2^k-1 knuth sedgewick
1000 7986 7987 5457 6182
2000 17963 17964 12364 14182
3000 28916 28917 19364 23021
4000 39916 39917 27084 32116
5000 51821 51822 35084 42116
6000 63821 63822 43084 52116
7000 75821 75822 51084 62116
8000 87821 87822 59084 72116
Les graphes correspondents :
0 1000 2000 3000 4000 5000 6000 7000 8000 90000
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000Resultats des (4) sequences sur des
tableaux Trié
Trié 2^k
Trié 2^k-1
Trié knuth
Trié sedgewick
Tailles des deonnées
Nbr
com
para
ison
On remarque que ; 1. Le cout de séquence de Shell et
Hibbard est presque le même.
2. Et selon ce que nous trouvons dans le cas des données triées la séquence de Knuth superforme la séquence de Sedgewick.
3. On peut dire que les (4) séquences donne une résultat acceptable en concernant l’amélioration entre eux .
tableau représente les résultats de les (4) séquence sur des tableaux triés à l’envers en plusieurs tailles :
Trié à l'envers
2^k 2^k-1 knuth sedgewick
100010175 10511 8550 9046
200022914 22947 18116 20437
300037501 38050 30380 33598
400051785 51403 44221 46599
500066016 65541 51491 58224
600081249 81303 63434 74305
700093690 94488 77616 89429
8000 87821 87822 59084 72116
Les graphes correspondent :
0 1000 2000 3000 4000 5000 6000 7000 8000 90000
20000
40000
60000
80000
100000
120000
140000
Resultats des (4) sequences sur des tableaux Trié à l'envers
Trié à l'envers 2^k
Trié à l'envers 2^k-1
Trié à l'envers knuth
Trié à l'envers sedgewick
Tailles des deonnées
Nbr
com
para
ison
On remarque que ; 1. 1. Le cout de séquence de
Shell et Hibbard reste presque le même.
2. Et selon ce que nous trouvons dans le cas des données triées à l’envers la séquence de Knuth reste aussi superforme la séquence de Sedgewick.
3. les (4) séquences donne une résultat attendue en concernant l’amélioration entre eux .
tableau représente les résultats de les (4) séquence sur des tableaux aléatoires en plusieurs tailles :
Aléatoire
2^k 2^k-1 knuth sedgewick
100012861 13239 12620 11711
200029535 29038 27270 26008
300046555 47297 44199 39303
400064211 68863 61680 53848
500084535 85597 79512 58224
6000103291 103974 101371 84369
7000120241 125980 118503 99830
8000140799 143409 136786 101339
Les graphes correspondents :
0 1000 2000 3000 4000 5000 6000 7000 8000 90000
20000
40000
60000
80000
100000
120000
140000
160000
Resultats des (4) sequences sur des tableaux Aléatoire
Aléatoire 2^k
Aléatoire 2^k-1
Aléatoire knuth
Aléatoire sedgewick
Tailles des deonnées
Nbr
com
para
ison
On remarque que ; 1. Le cout de séquence de
Hibbard surmonte la séquence de Shell ce qui montre l’amélioration de séquence de Hibbard p à p Shell.
2. selon ce qu’on trouve dans le cas des données aléatoire la séquence de Sedgewick montre sa superforme par-à-port la séquence de Knuth (résultat optimal).
3. On peut dire que les (4) séquences donne une résultat agréable concernant l’amélioration entre eux .
ConclusionEnfin de ce pratique, les séquences étudié
donne des résultats convenables et prévus.
A partir de ces résultats nous constatons que le tri par Shell passe par des améliorations (séquences) pour qu’il devenue de ce meilleur complexité (jusqu’à ce jour).
Finalement l’amélioration de tri par Shell reste un problème ouvert qui peut être un jour on trouve une amélioration Optimale.
Merci