Tri par insertion
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
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.