[Plan du site] Vous êtes ici --- > Le Site du Zéro > Les tutoriels > Non-Officiels > Programmation > Algorithmique > Le tri de Shell > Lecture des commentaires

Le tri de Shell

Vous devez être inscrit pour pouvoir poster des messages

Page : 1

Pseudo

Commentaire

Page : 1

Nanoc

# Posté le 21/03/2007 à 19:09:41 - Ce membre n'a pas mis de note

Apprenez à utiliser la STL !!
Avatar

Groupe : Membres

Si vous avez des idées d'améliorations ou des remarques, n'hésitez pas !

Exercices de C++ pour tous les niveaux !
Mes tutos: Tri de Shell --- [C++] Manipulateurs de flux
--- [C++] Notions avancées (suite du cours de M@teo21)

Gurthang

# Posté le 18/05/2007 à 21:30:34 - Ce membre a mis la note : 15

Groupe : Membres

Pour le calcul de complexité, quand tu dis que c'est en n^1.5, c'est en fait log3(2) non ?
Sinon, on peut quand même lui préférer le tri par fusion ou le tri rapide

J'éditerai ce post et je mettrai une note quand je l'aurais lu en détails

Peut etre qu'une implémentation en CamL, OCamL ou Pascal serait intéressante ?

Gurthang

# Posté le 19/05/2007 à 07:22:38 - Ce membre a mis la note : 15

Groupe : Membres

Bon j'arrive pas à éditer mon post donc je fais un doublon, c'est pas grave

Euh déjà pour la fin, pour la complexité, j'ai deux p'tits trucs à dire :

Déjà, au lieu de parler de la notation de Landau (ou un truc commme ca^^) tu pourrais peut etre tout simplement parler de prépondérance : c'est la fonction "la plus grande" quand n tend vers l'infini. Tu l'dis mais je pense que ca suffit, pas besoin de parler de notations ni rien. La plupart des lycéens savent ce que veut dire "prépondérant quand n tend vers l'infini". Enfin, c'est un détail

Ensuite, f(x)=O(x²) <=> Il existe un C et il existe un A tel que pour tout x > A, f(x)<M*x²

Comme je l'ai dit plus haut, une implémentation en CamL ou en Pascal serait bien, car ce sont des langages mieux adaptés.

Et pour finir, dans ton tableau final résumant les différents tris qui existent, tu a oublié le tri par dénombrement et le tri par fusion. Ce dernier est pourtant intéressant car il est en nlog(n), dans le pire ou le meilleur des cas.
Et en français, le quick sort s'appelle le tri rapide

Voila voila, ca reste un bon tuto pour les non matheux, donc j'mets 15 !

Nanoc

# Posté le 19/05/2007 à 12:43:15 - Ce membre n'a pas mis de note

Apprenez à utiliser la STL !!
Avatar

Groupe : Membres

Hello,

Merci pour tes commentaires

Citation : Gurthang

Pour le calcul de complexité, quand tu dis que c'est en n^1.5, c'est en fait log3(2) non ?

En effet mais bon log3(2) = 1.58496250072 qui est presque 1.5 et c'est plus court à écrire que O(n^log3(2))

Citation : Gurthang

Sinon, on peut quand même lui préférer le tri par fusion ou le tri rapide

Oui bien sûr, mais ces 2 tris sont plus difficile à implémenter. (bien que le tri rapide (Quicksort) soit présent dans la STL pour le C++ par exemple)

Citation : Gurthang

Déjà, au lieu de parler de la notation de Landau (ou un truc commme ca^^) tu pourrais peut etre tout simplement parler de prépondérance : c'est la fonction "la plus grande" quand n tend vers l'infini. Tu l'dis mais je pense que ca suffit, pas besoin de parler de notations ni rien. La plupart des lycéens savent ce que veut dire "prépondérant quand n tend vers l'infini". Enfin, c'est un détail

Mmmh si tu le dis. Mais moi en Suisse (Eh oui y en a aussi sur le SdZ

), je n'en avais jamais entendu parler sous cette forme avant ma première année d'uni. En tout cas pas pour comparer des fonctions

Citation : Gurthang

Ensuite, f(x)=O(x²) <=> Il existe un C et il existe un A tel que pour tout x > A, f(x)<M*x²

En effet, je vais rajouter ça, peut-être que ça clarifiera. Je ne voulais pas mettre trop de symboles mathématiques mais comme tu le dis plus haut tous les français connaissent ça

Citation : Gurthang

Comme je l'ai dit plus haut, une implémentation en CamL ou en Pascal serait bien, car ce sont des langages mieux adaptés.

En effet, une implémentation dans un langage "neutre" serait certainement mieux. Mais ça pose de nombreux problème:
Caml n'est pas forcément compréhensible par tout le monde.
Il est difficile d'écrire quelque chose d'indépendant de tout langage.

Ensuite je ne connais pas du tout le pascal et finalement le C/C++ est mieux adapté pour le SdZ, car ce sont les langages les plus utilisés sur le site de manière générale.

Mais sur le fond je suis d'accord avec toi, il faudrait une représentation plus "neutre", plus "algorithmique".
Citation : Gurthang

Et pour finir, dans ton tableau final résumant les différents tris qui existent, tu a oublié le tri par dénombrement et le tri par fusion. Ce dernier est pourtant intéressant car il est en nlog(n), dans le pire ou le meilleur des cas.
Et en français, le quick sort s'appelle le tri rapide

Le tri par dénombrement (tri par panier ou tri par comptage) ne fais pas partie de ma liste pour 2 raisons:

Il ne permet de trier que des entiers (Ou toute liste assimilable à des entiers)
Sa complexité ne dépend pas de la taille de la liste (ou pas uniquement)

J'ai en effet oublié le tri fusion, chose que je vais corriger.
Et pour le tri rapide, je préfère l'appellation "Quicksort" qui est son nom habituel.

Merci pour tes remarques constructives

Nanoc

Exercices de C++ pour tous les niveaux !
Mes tutos: Tri de Shell --- [C++] Manipulateurs de flux
--- [C++] Notions avancées (suite du cours de M@teo21)

Zmatt

# Posté le 27/05/2007 à 19:00:51 - Ce membre n'a pas mis de note

Groupe : Membres

Tuto interressant et bien conçu

mais je me demande à quoi sert ce tri en pratique ?
Puisque le quicksort ou le tri par fusion sont pas très compliqué à implémenter, mieux vaut se servir s'eux non

?

Ah oui et sinon pourquoi la complexité est de O(x^(ln3/ln2)) ? je vois bien de quelle formule ça vient

c'est le fameux diviser pour regner. Mais pourquoi le problème est ramené à 3 problèmes de taille n/2 ?

Aldrien

# Posté le 28/05/2007 à 11:01:30 - Ce membre n'a pas mis de note

Zordania Forever

Groupe : Membres

Pourquoi coller un "o" dans le QCM? alors que personne ne sait ce que c'est, enfin c'est pas grave mais bon!

Sinon dans le monde des maths on se sert pas beaucoup du O mais beaucoup du ~ et du o apres en informatique si vous vous servez du O tant mieux

Nanoc

# Posté le 28/05/2007 à 11:35:37 - Ce membre n'a pas mis de note

Apprenez à utiliser la STL !!
Avatar

Groupe : Membres

Hello,

Merci pour vos commentaires,

Citation : Zmatt

mais je me demande à quoi sert ce tri en pratique ?
Puisque le quicksort ou le tri par fusion sont pas très compliqué à implémenter, mieux vaut se servir s'eux non

Tout à fait d'accord, il vaut mieux s'en servir puisqu'ils sont meilleurs (et dans la STL pour le quicksort) mais ils sont plus compliqué à implémenter que le tri de Shell.

Citation : Aldrien

Pourquoi coller un "o" dans le QCM? alors que personne ne sait ce que c'est, enfin c'est pas grave mais bon!

En effet, mais si tu sais pas ce que c'est, c'est que c'est sûrement faux.

Citation : Aldrien

Sinon dans le monde des maths on se sert pas beaucoup du O mais beaucoup du ~ et du o apres en informatique si vous vous servez du O tant mieux

Alors là pas d'accord. Les o et O sont plus utilisés que le ~ pour les fonctions puisqu'ils donnent plus d'informations.

f(x) est un O(x^2) si il existe C t. f(x) < C * x^2 pour tout x.
f(x) est un o(x^2) si la limite quand (x->0) de f(x)/x^2 est 0.

Alors que le ~ ne donne pas d'information sur le comportement asymptotique de f.

Exercices de C++ pour tous les niveaux !
Mes tutos: Tri de Shell --- [C++] Manipulateurs de flux
--- [C++] Notions avancées (suite du cours de M@teo21)

Aldrien

# Posté le 28/05/2007 à 21:12:10 - Ce membre n'a pas mis de note

Zordania Forever

Groupe : Membres

Bien sur que si que le ~ donne la nature du comportement!

D'ailleurs ce n'est pas qu'asymptotique, c'est vrai aussi en tout point.

Vois ça comme un quotient en prenant la limite au point a

f/g = 0 f=o(g) en a
f/g = C f=O(g) en a (avec C = constante)
f/g = 1 f~g en a

Evidement ça puxx avec des fonctions exprimables du genre exp, puissance, ln mais c'est tres bien les ~

Si tu as une fonction tordu (voir implicite) et que tu sais qu'elle est équivalente a exp(-t/58) en +inf c'est beaucoup plus informatif que de savoir que c'est un 0 ou un o.

Asymptotiquement racine(x) est un o de l'exp mais ça renseigne pas vraiment sur sa manière de se comporter en plus l'infini!

Citation : l'auteur

f(x) est un O(x^2) si il existe C t. f(x) < C * x^2 pour tout x.
f(x) est un o(x^2) si la limite quand (x->0) de f(x)/x^2 est 0.

Oulalalala d'ailleurs ça c'est très faux.

Etre un o ou un O c'est surtout utile localement et pas globalement. Attention a ne pas dire n'importe quoi!

Si tu prend un fonction vilain f qui vaut exp(-x) sur R- et x sur R+ alors oui f=O(x) en plus l'infini mais il n'existe pas de constante machin telle que pour tout x.... puisque sur R- c'est faux!

mrbuisson

# Posté le 04/06/2007 à 11:27:14 - Ce membre n'a pas mis de note

Groupe : Membres

quand tu met :
Code : C

do{
pas = (3 * pas) + 1
}while(pas<n);

le pas a la fin de la boucle est supérieur a n !!!!

cela n'est pas génant mais tu doit donc décrementer le pas avant de l'utiliser

ce qui donnerais Code : C

void tri_shell(int tableau[],int n)
{
int pas(0), j, valeur; //Création et initialisation des variables

do{ //Calcul du premier pas
pas=3*pas+1;
}while(pas<n);//lorsceque la boucle s'arrete on a pas>=n

while(pas!=0) //Tant que le pas est plus grand ou égal à 1
{
pas=(pas-1)/3; //On décrémente le pas (changement de place du décrement)
for (int i(pas);i<n;i++) // On parcourt la liste
{
valeur=tableau[i]; //il y aurait depassement de mémoire ici
j=i;

while((j>(pas-1)) && (tableau[j-pas]>valeur)) //Et on échange les valeurs mal-placées
{
tableau[j]=tableau[j-pas];
j=j-pas;
}
tableau[j]=valeur;
}
//le décrement était ici
}
}

j'ai bien vérifié aussi je ne pense pas etre dans l'erreur mais bon je ne peu jurer de rien =)

sinon bon tuto j'ai bien aimé aussi les lien en fin

La nature les fleurs et les ordinateurs

Nanoc

# Posté le 05/06/2007 à 08:52:22 - Ce membre n'a pas mis de note

Apprenez à utiliser la STL !!
Avatar

Groupe : Membres

@Aldrien:

Entièrement d'accord, mais il se trouve que ce qui nous intéresse c'est le comportement asymptotique de la "fonction" (ici algorithme) puisque de toute façon, l'algorithme est en n^2 que si n tend vers l'infini.
Donc la notation en O se justifie et ce n'est pas pour rien qu'elle est utilisée en algorithmie plutot que le environ.

De plus les algorithmes n'ont jamais des complexité tel que l'exemple que tu cites (où en effet un O n'a de sens que sur R+ ou R-), les complexités sont principalement du type:
O(n^a)
O(log n)
O(n * log n)
O(exp n)
O(n !)
...

pour plus d'infos:

http://fr.wikipedia.org/wiki/Complexit%C3%A9_algorithmique

@ Mrbuisson:
En effet, le pas est plus grand que n après le passage dans la boucle while.

Mais ça ne pose pas de problème, puisque
Code : C++

for (int i(pas);i<n;i++)

empêche d'entrer dans la liste si i (qui vaut pas) est plus grand que n.

Donc on saute la partie où tu suspectais un segmentation fault.

Exercices de C++ pour tous les niveaux !
Mes tutos: Tri de Shell --- [C++] Manipulateurs de flux
--- [C++] Notions avancées (suite du cours de M@teo21)

Magorath

# Posté le 29/06/2007 à 13:00:26 - Ce membre a mis la note : 20

Groupe : Membres

Merci,

Je cherchais justement une explication sur cette méthode pour mes cours.

Magorath

brastir

# Posté le 14/11/2007 à 17:53:14 - Ce membre a mis la note : 20

Groupe : Membres

Merci pour ce super tuto qui nous monttre le trie shell drolement utile. Merci Nanoc. Je te réquonpense donc d'un 20/20.

le grand schtroumpf

# Posté le 29/03/2008 à 15:46:32 - Ce membre a mis la note : 18

Si vis pacem, para bellum!

Groupe : Membres

Bon tutorial!

Cependant, je pense que dans la section complexité, il aurait été plus intéressant de donner des bornes asymptotiquement approchée de la complexité, plutôt qu'une borne supérieure asymptotique(ça serait plus rigoureux)...

Car la complexité dans le cas moyen est aussi en O(n²), mais elle n'est pas en Θ(n²)...

sinon les explications sont claires globalement, très bon tuto...

Cutlass fury(furie du sabre) de Vyse

Cliquez pour agrandir

yoch

# Posté le 27/11/2008 à 23:33:07 - Ce membre n'a pas mis de note

Groupe : Membres

Très bon tuto !

J'ai effectué quelques mesures, l'amélioration est vraiment spectaculaire vis-a-vis d'un tri insertion standard.

Je poste le code en pur C pour qui serait intéressé (j'en ai profite pour le mettre a mon gout

) :

Code : C

void tri_shell (int* tableau, int n)
{
    int pas, i, j, valeur;

    /* calcul du premier pas */
    for (pas=0; pas<n; pas = (3*pas)+1);

    /* tant que le pas est superieur a 0 */
    while (pas!=0)
    {
        for (i = pas; i<n; i++)
        {
            valeur = tableau[i];
            for ( j=i; j > (pas-1) && tableau[j-pas] > valeur; j-=pas )
            {
                tableau[j] = tableau[j-pas];
            }
            tableau[j] = valeur;
        }
        /* on décrémente le pas */
        pas = (pas-1)/3;
    }
}

Tutos en ligne
Comprendre la messagerie électronique
Bloquer du contenu avec le fichier hosts
Modifier une application Windows

Vous devez être inscrit pour pouvoir poster des messages

Tutoriels

Communauté

Mon compte

Recherche

Livre d'or

Publicité

Le tri de Shell