Tri par insertion
Soyez le premier à donner votre avis sur cette source.
Snippet vu 16 738 fois - Téléchargée 25 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
A voir également
- Tri par insertion php
- Tri par selection php - Meilleures réponses
- Php tri - Meilleures réponses
- Tri par insertion java - Forum - Java
- Tri par insertion c# - Guide
- Tri_par_insertion - Codes sources - C / C++ / C++.NET (Maths & Algorithmes)
- C / C++ / C++.NET : Tri par insertion avec sentinelle - CodeS SourceS - Guide
- Tri par insertion - Codes sources - Visual Basic / VB.NET (Tutoriels)
Commentaires
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!!!
- Messages postés
-
1804
- Date d'inscription
- mardi 15 juillet 2003
- Statut
- Membre
- Dernière intervention
- 22 septembre 2009
4"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)
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???
Et sinon oui ça trie aussi les mots !
- Messages postés
-
1804
- Date d'inscription
- mardi 15 juillet 2003
- Statut
- Membre
- Dernière intervention
- 22 septembre 2009
4Vous 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.