Tri par insertion
Soyez le premier à donner votre avis sur cette source.
Snippet vu 20 081 fois - Téléchargée 27 fois
Contenu du snippet
Hello tout le monde alors je vous poste une petite fonction que j'ai faite qui permet de faire un tri par insertion
L'exemple suivant permet d'obtenir :
Avant :
543, 118, 328, 11, 5, 989, 1831, 33, 411, 55, 44, 291, 49
Après :
5, 11, 33, 44, 49, 55, 118, 291, 328, 411, 543, 989, 1831
La fonction est simple, elle prend en argument un tableau de valeurs, non trié, et renvoi un tableau, trié.
- Le nombre de comparaisons nécessaires est de l'ordre de N²/4.
- Le nombre moyen d'échanges est de l'ordre de N²/2.
(N étant le nombre de valeurs)
Son temps d'éxecution est linéaire, et dans un cas moyen sa complexité temporelle est de Theta(n²)
Si vous voulez voir les étapes, décommentez les Echos.
Merci de me donner une bonne note :P
Bon bah pas de bugs connus..
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.
Postez vos commentaires..
DarkM
L'exemple suivant permet d'obtenir :
Avant :
543, 118, 328, 11, 5, 989, 1831, 33, 411, 55, 44, 291, 49
Après :
5, 11, 33, 44, 49, 55, 118, 291, 328, 411, 543, 989, 1831
La fonction est simple, elle prend en argument un tableau de valeurs, non trié, et renvoi un tableau, trié.
- Le nombre de comparaisons nécessaires est de l'ordre de N²/4.
- Le nombre moyen d'échanges est de l'ordre de N²/2.
(N étant le nombre de valeurs)
Son temps d'éxecution est linéaire, et dans un cas moyen sa complexité temporelle est de Theta(n²)
Si vous voulez voir les étapes, décommentez les Echos.
Merci de me donner une bonne note :P
Source / Exemple :
<?php
function display($array) {
$total = count($array);
foreach($array as $key => $valeur) {
if($key == ($total - 1))
{
echo("$valeur");
}
else
{
echo("$valeur, ");
}
}
}
function isort($unsorted) {
$j = 1; //Case analysée
$n = count($unsorted);
//echo("<br><br> Start : $n cases <br><br>");
while($j != $n)
{
//echo("Boucle numero $j on étudie la case $j = ".$unsorted[$j]."<br>");
$i = $j - 1; //Case étudiée par rapport à l'analysée
$cle = $unsorted[$j];
while(($i > -1) && ($unsorted[$i] > $cle))
{
//echo(" |--- Sous-boucle i = $i <br>");
$unsorted[$i + 1] = $unsorted[$i];
$i = $i - 1;
}
$unsorted[$i + 1] = $cle;
$j++;
}
return $unsorted;
}
$unsorted = array(543,118,328,11,5,989,1831,33,411,55,44,291,49 );
echo("Avant :<br>");
display($unsorted);
echo("<br>Après :<br>");
display(isort($unsorted));
?>
Conclusion :
Bon bah pas de bugs connus..
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.
Postez vos commentaires..
DarkM
12 avril 2007 à 17:09
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!!!
12 avril 2007 à 15:26
"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)
12 avril 2007 à 13:58
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???
3 avril 2007 à 12:53
Et sinon oui ça trie aussi les mots !
3 avril 2007 à 10:53
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.