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

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
Ajouter un commentaire Commentaires
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 6
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 6
3 avril 2007 à 10:53
Teste, tu verras bien ;o)
Afficher les 19 commentaires

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.