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

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

Ajouter un commentaire

Commentaires

Messages postés
148
Date d'inscription
dimanche 25 janvier 2004
Statut
Membre
Dernière intervention
21 janvier 2009

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!!!
Messages postés
1804
Date d'inscription
mardi 15 juillet 2003
Statut
Membre
Dernière intervention
22 septembre 2009
4
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)
Messages postés
148
Date d'inscription
dimanche 25 janvier 2004
Statut
Membre
Dernière intervention
21 janvier 2009

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???
Messages postés
37
Date d'inscription
dimanche 15 mai 2005
Statut
Membre
Dernière intervention
21 septembre 2009

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 !
Messages postés
1804
Date d'inscription
mardi 15 juillet 2003
Statut
Membre
Dernière intervention
22 septembre 2009
4
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.