TRI PAR INSERTION

DarkM60 Messages postés 37 Date d'inscription dimanche 15 mai 2005 Statut Membre Dernière intervention 21 septembre 2009 - 12 juin 2006 à 14:45
zoukozouko Messages postés 148 Date d'inscription dimanche 25 janvier 2004 Statut Membre Dernière intervention 21 janvier 2009 - 12 avril 2007 à 17:09
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/38074-tri-par-insertion

zoukozouko Messages postés 148 Date d'inscription dimanche 25 janvier 2004 Statut Membre Dernière intervention 21 janvier 2009
12 avril 2007 à 17:09
Ok, merci beaucoup
Je vais aller mater la doc. Si je reviens sur le forum c'est soit pour donner la solution détaillée, soit parce que j'ai rien compris à la doc.
Merci en tout cas!!!
cs_PaDa Messages postés 1804 Date d'inscription mardi 15 juillet 2003 Statut Membre Dernière intervention 22 septembre 2009 5
12 avril 2007 à 15:26
array_multisort() te permettra de faire ce que tu veux.

"array_multisort sert à trier simultanément plusieurs tableaux, ou bien à trier un tableau multi-dimensionnel, suivant l'une ou l'autre de ses dimensions." (extrait de la doc php)
zoukozouko Messages postés 148 Date d'inscription dimanche 25 janvier 2004 Statut Membre Dernière intervention 21 janvier 2009
12 avril 2007 à 13:58
C'est sûr qu'il n'ya pas plus rapide que la fonction sort de php (peut etre un quick sort)
Quelqu'un saurait-il comment obtenir le code source du "sort" de php?
Le pb c'est que j'ai deux tableaux : un avec des num tel, l'autre avec les prénoms.
Quand je tri l'un, j'aimerais que l'autres se tri dans le même oprdre, pour garder la correspondance prénom/numéro pour un même indice (avant et après tri)
Quelqu'un peut m'aider???
DarkM60 Messages postés 37 Date d'inscription dimanche 15 mai 2005 Statut Membre Dernière intervention 21 septembre 2009
3 avril 2007 à 12:53
A Konkerouf >> C'est un des premiers algos que j'ai codé. J'ai jamai svoulu en inventer un j'ai bien précisé que c'était un tri par insertion...Si tu ne sais pas lire c'est pas mon problème... Dans ce cas suffit d'utiliser sort()... Bref c'est juste à but didactique. 'fin bon.

Et sinon oui ça trie aussi les mots !
cs_PaDa Messages postés 1804 Date d'inscription mardi 15 juillet 2003 Statut Membre Dernière intervention 22 septembre 2009 5
3 avril 2007 à 10:53
Teste, tu verras bien ;o)
anouartepdr Messages postés 11 Date d'inscription dimanche 24 avril 2005 Statut Membre Dernière intervention 13 avril 2007
3 avril 2007 à 08:35
la fonction permet également de tier des mots ou quoi?
Konkerouf Messages postés 3 Date d'inscription jeudi 17 février 2005 Statut Membre Dernière intervention 26 octobre 2006
26 oct. 2006 à 23:53
Mmmmh perso ce code me dérange pour plusieurs raisons:

-Il n'y a aucune récursivité la dedans. Tu crois qu'une boucle imbriquée dans une boucle est de la récursivité et tu te trompes. Une fonction récursive est une fonction qui s'appelle elle-même (pour justement éviter d'utiliser une boucle). Complètement inutile dans le cas d'un tri de tableau. La récursivité est très souvent une mauvaise solution. Ce sont des appels dans la pile ce qui coute cher en temps. Il n'y a que certains cas ou c'est plus avantageux de les utiliser et ce n'est surement pas le cas d'un tri de tableau (je pense aux opérations sur les arbres par exemple).

-Tu devrais mieux nommer tes variables. Le fait de les appeler $i et $j rend ton code assez incompréhensible, surtout pour un débutant. N'oublie pas que lire le code de quelqu'un d'autre est quelque chose d'assez lourd et de plutot compliqué quand on débute (meme si le code est simple).

-J'aime pas du tout cet algo en lui même. Pourquoi vouloir en "inventer" un nouveau alors que des algos très performant existe déja? (exemple: tri-bulle). Autant cela peut être nécessaire lors d'écriture de méthodes (ou fonctions, mais pourquoi faire du procédural quand on a la possibilité de faire de l'objet?) métiers, autant un algo de tri de tableau ça ne l'est pas.
TheSin Messages postés 331 Date d'inscription mardi 12 novembre 2002 Statut Membre Dernière intervention 10 février 2009
13 juin 2006 à 13:35
Oui, je suis d'accord avec toi xque19.
Il y a bien une boucle itérative While, mais aucune récursivité.
On se tromperait ?
xque19 Messages postés 47 Date d'inscription dimanche 20 février 2005 Statut Membre Dernière intervention 19 novembre 2006 1
13 juin 2006 à 10:25
Salut,

Moi personnellement, je n'arrive pas à voir où se trouve le côté récursif de cette fonction, je n'ai jamais eu à utiliser la recusivité en php mais bon si c'est le même principe de mise en oeuvre qu'ailleur, il ne devrait pas y avoir de boucle itérative "while" dans la fonction isort, et je ne vois pas non plus d'appels imbriqué, enfin peut-être que je me trompe.

++
coockiesch Messages postés 2268 Date d'inscription mercredi 27 novembre 2002 Statut Membre Dernière intervention 13 septembre 2013 4
13 juin 2006 à 09:09
Héhé, malalam fan d'escalade?
A part ca ce qui serait intéressant c'est de regrouper dans une même source plusieurs méthodes de tri... :)

@++

R@f
cs_manouille Messages postés 73 Date d'inscription vendredi 29 août 2003 Statut Membre Dernière intervention 22 juin 2007
13 juin 2006 à 08:58
Sinon pour info :

sort() trie le tableau array. Les éléments seront triés du plus petit au plus grand.

Constantes de type de tri :


SORT_REGULAR : compare les éléments normalement (ne modifie pas les types)

SORT_NUMERIC : compare les éléments numériquement

SORT_STRING : compare les éléments comme des chaînes de caractères


rsort -- Trie un tableau en ordre inverse
malalam Messages postés 10839 Date d'inscription lundi 24 février 2003 Statut Membre Dernière intervention 2 mars 2010 25
13 juin 2006 à 06:42
"Pour le array dans ce que j'utilise moi c'est testé vu que j'utilise un formulaire pour rentrer les chiffres mais la c'est juste pour montrer."

heu ouais m'enfin, montrer, c'est aussi montrer BIEN. Montrer de la récursivité, de l'algo, c'est aussi montrer comment ne pas sortir des bornes, comment ne pas faire un dépassement. Tu dis toi-même que c'est à but pédagogique. T'aimerais, toi, avoir un prof d'escalade qui te montre comment grimper, comment trouver les bonnes prises...mais ne te montre pas comment t'assurer?
Moi pas.
kankrelune Messages postés 1293 Date d'inscription mardi 9 novembre 2004 Statut Membre Dernière intervention 21 mai 2015
13 juin 2006 à 03:19
Le niveau est 2, initié, car bien que les fonctions utilisées soit de bas niveau, ce code peut s'avérer complexe pour un débutant ne connaissant pas les bases de la récursivité en php.


o_Ô

Mouais... je suis pas d'accord... on peut être débutant et savoir ce qu'est la récursivité qui est loin d'êtree un concept propre à php... .. .

@ tchaOo°
DarkM60 Messages postés 37 Date d'inscription dimanche 15 mai 2005 Statut Membre Dernière intervention 21 septembre 2009
12 juin 2006 à 19:09
Ce code est entierement à but pédagogique, en effet avec la fonction sort on peux trier facilement, mais la ça permet surtout de faire des controles sur le temps d'execution et de comparer les différentes méthodes de tris, car on peux placer des controles en pleins millieux des fonctions récursives..

Pour le array dans ce que j'utilise moi c'est testé vu que j'utilise un formulaire pour rentrer les chiffres mais la c'est juste pour montrer.
malalam Messages postés 10839 Date d'inscription lundi 24 février 2003 Statut Membre Dernière intervention 2 mars 2010 25
12 juin 2006 à 16:13
Hello,

pour ma part, j'espère en effet que le but de ce code est surtout de montrer un algo, parce que sinon, il ne sert strictement à rien.
Ceci dit, ok, c'est un algo de tri par insertion :-)
Attention quand même aux tableaux indexés "manuellement" : $aArray array (2> 127, 3 => 854, 8 => 546, 12 => 1021);
Ton code risque d'avoir du mal ;-) Faudrait tester l'existence d'un index, si tu ne veux pas risquer un dépassement.
cs_PaDa Messages postés 1804 Date d'inscription mardi 15 juillet 2003 Statut Membre Dernière intervention 22 septembre 2009 5
12 juin 2006 à 15:20
Autre chose, tu gagnerais surement à éviter le count() au début.
Fais ta boucle sur du (isset($unsorted[$j])) par exemple.
Bien que je pense pas que le but était de concurrencer php niveau performance ;)
coockiesch Messages postés 2268 Date d'inscription mercredi 27 novembre 2002 Statut Membre Dernière intervention 13 septembre 2013 4
12 juin 2006 à 15:09
Salut!
L'idée est bien! :)

Mais PHP a des fonctions toutes faites plus efficaces: j'ai fais trier le tableau que tu donnes 10000 fois avec ta fonction et la fonction sort de PHP:
temps d'exécution:
- ta fonction: 1.51
- fonction de php: 0.04

@++

R@f
cs_PaDa Messages postés 1804 Date d'inscription mardi 15 juillet 2003 Statut Membre Dernière intervention 22 septembre 2009 5
12 juin 2006 à 15:01
Je pense que ta fonction display peut être simplifiée:

function display2($array=array()) {
echo implode(', ',$array);
}

(avec un array_values en plus si tu veux que ca marche sur les tableaux associatifs, mais d'après ta fonction, ce n'est pas le cas)

Pas regardé le sorting mais si ca marche.. :p

Bonne continuation
DarkM60 Messages postés 37 Date d'inscription dimanche 15 mai 2005 Statut Membre Dernière intervention 21 septembre 2009
12 juin 2006 à 14:45
J'ajoute que la fonction permet également de tier des mots :

Avant :
Cette, fonction, permet, egalement, de, trier, des, mots, selon, les, lettres, qui, les, composent, voila
Après :
Cette, composent, de, des, egalement, fonction, les, les, lettres, mots, permet, qui, selon, trier, voila
Rejoignez-nous