CodeS-SourceS est hébergé par Frontier.fr

Cliquez ici pour mettre ce site au démarrage de votre navigateur

AccueilCodesTutorielsForumsEmploiLivresGuide achatConnexion

begin process at 2009 07 05 11:24:50

SILVERLIGHT 3 : COMMUNICATION ET MULTICAST par KooKiz

[PERSO] DéCOUVERTES ESTIVALES : LINUX (PART I) par FREMYCOMPANY

[REFACTORING] RESHARPER POUR VISUAL STUDIO 2010 (PREVIEW) par tja

[REFACTORING] ANALYSER VOS EXCEPTIONS AVEC RESHARPER EXCEPTIONAL par tja

SHAREPOINT 2007 : PATTERNS & PRACTICES SHAREPOINT GUIDANCE par phil

RE : IMAGE ET LISTE DE NOM par Bling 182

RE : COMMENT SECURIRISé UNE BD? par lionceau79

RE : INTEGRATION FICHIER SWF AVEC FONCTION INCLUDE PHP par lemarge

RE : PROBLEME AVEC LES ROW par aerobi

RE : FILTRER UNE TABLE POUR NE PAS AVOIR DE DOUBLURE par jzeel

+ de logiciels à télécharger

1 464 589 membres
91 nouveaux aujourd'hui
15 045 membres club

Trouver une ressource

Trouvez une ressource parmi 40 096 codes, 1 302 937 messages d'aide etc...

Recherche: dans [ Dernières recherches ]

Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

TRI PAR INSERTION

Information sur la source

Catégorie :Maths & Algorithmes Classé sous : tri, insertion, triage, trier Niveau : Initié Date de création : 12/06/2006 Date de mise à jour : 12/06/2006 14:43:29 Vu : 8 653

Auteur : DarkM60

Ecrire un message privé

Note :
Aucune note

Commentaire sur cette source (19)

Ajouter un commentaire et/ou une note

Description

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

<?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(" Start : $n cases ");
while($j != $n)
{
//echo("Boucle numero $j on étudie la case $j = ".$unsorted[$j]." ");
$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 ");
$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 : ");
display($unsorted);
echo(" Après : ");
display(isort($unsorted));
?>

<?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

Historique

12 juin 2006 14:43:30 :: Ajout d'une fonction "display" pour une meilleur lisibilitée des tableaux en sortie.

Sources du même auteur

KORREKTOR, FAÎTES TRAVAILLER VOS VISITEURS !

ORDRE DES LETTRES DANS UN MOT, ETUDE DE L'UNIVERSITÉ DE CAMB...

BARRE DE POURCENTAGE ADAPTABLE (LIBRAIRIE GD UTILISÉE)

LIRE UNE DATABASE EN TXT

Toutes les sources de DarkM60

Sources de la même categorie

EVALUER UNE EXPRESSION À PARTIR D'UNE CHAINE DE CARACTÈRE par TheWeasel47

FONCTION EQUATION LÉGÈRE par ff5

TRACEUR DE COURBE EN COORDONNÉES CARTÉSIENNES (MAJ) par fredbonmatin

CONVERTIR LES RÉFÉRENCES DE COLONNE EXCEL DE CHIFFRE EN LETT... par computman007

CALCULE GÉOMÉTRIQUE par firesamu

Toutes les sources de la catégorie Maths & Algorithmes

Sources en rapport avec celle ci

PORTAGE PDO DE MES ANCIENNES PUBLICATIONS par 8Tnerolf8

AJOUT VALEUR CHAMP ENUM par Tetechercheuse

FONCTION D'AFFICHAGE DE DONNÉES MYSQL par Snakegun

TRIE ET FILTRE UNIVERSEL DE REQUÊTES DANS UN FORMULAIRE À PA... par 8Tnerolf8

TRI PAR TYPE DE FICHIER / EXTENSION par Evangun

Commentaires et avis

Commentaire de DarkM60 le 12/06/2006 14:45:21

J'ajoute que la fonction permet également de tier des mots :

Avant :
Cette, fonction, permet, egalement, de, trier, des, mots, selon, les, lettres, qui, les, composent, voila
Après :
Cette, composent, de, des, egalement, fonction, les, les, lettres, mots, permet, qui, selon, trier, voila

Commentaire de PaDa le 12/06/2006 15:01:50

Je pense que ta fonction display peut être simplifiée:

function display2($array=array()) {
echo implode(', ',$array);
}

(avec un array_values en plus si tu veux que ca marche sur les tableaux associatifs, mais d'après ta fonction, ce n'est pas le cas)

Pas regardé le sorting mais si ca marche.. :p

Bonne continuation

Commentaire de coockiesch le 12/06/2006 15:09:04

Salut!
L'idée est bien! :)

Mais PHP a des fonctions toutes faites plus efficaces: j'ai fais trier le tableau que tu donnes 10000 fois avec ta fonction et la fonction sort de PHP:
temps d'exécution:
- ta fonction: 1.51
- fonction de php: 0.04

@++

R@f

Commentaire de PaDa le 12/06/2006 15:20:31

Autre chose, tu gagnerais surement à éviter le count() au début.
Fais ta boucle sur du (isset($unsorted[$j])) par exemple.
Bien que je pense pas que le but était de concurrencer php niveau performance ;)

Commentaire de malalam le 12/06/2006 16:13:08 administrateur CS

Hello,

pour ma part, j'espère en effet que le but de ce code est surtout de montrer un algo, parce que sinon, il ne sert strictement à rien.
Ceci dit, ok, c'est un algo de tri par insertion :-)
Attention quand même aux tableaux indexés "manuellement" : $aArray = array (2 => 127, 3 => 854, 8 => 546, 12 => 1021);
Ton code risque d'avoir du mal ;-) Faudrait tester l'existence d'un index, si tu ne veux pas risquer un dépassement.

Commentaire de DarkM60 le 12/06/2006 19:09:55

Ce code est entierement à but pédagogique, en effet avec la fonction sort on peux trier facilement, mais la ça permet surtout de faire des controles sur le temps d'execution et de comparer les différentes méthodes de tris, car on peux placer des controles en pleins millieux des fonctions récursives..

Pour le array dans ce que j'utilise moi c'est testé vu que j'utilise un formulaire pour rentrer les chiffres mais la c'est juste pour montrer.

Commentaire de kankrelune le 13/06/2006 03:19:39

[quote]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.[/quote]

o_Ô

Mouais... je suis pas d'accord... on peut être débutant et savoir ce qu'est la récursivité qui est loin d'êtree un concept propre à php... .. .

@ tchaOo°

Commentaire de malalam le 13/06/2006 06:42:17 administrateur CS

"Pour le array dans ce que j'utilise moi c'est testé vu que j'utilise un formulaire pour rentrer les chiffres mais la c'est juste pour montrer."

heu ouais m'enfin, montrer, c'est aussi montrer BIEN. Montrer de la récursivité, de l'algo, c'est aussi montrer comment ne pas sortir des bornes, comment ne pas faire un dépassement. Tu dis toi-même que c'est à but pédagogique. T'aimerais, toi, avoir un prof d'escalade qui te montre comment grimper, comment trouver les bonnes prises...mais ne te montre pas comment t'assurer?
Moi pas.

Commentaire de manouille le 13/06/2006 08:58:50

Sinon pour info :

sort() trie le tableau array. Les éléments seront triés du plus petit au plus grand.

Constantes de type de tri :

SORT_REGULAR : compare les éléments normalement (ne modifie pas les types)

SORT_NUMERIC : compare les éléments numériquement

SORT_STRING : compare les éléments comme des chaînes de caractères

rsort -- Trie un tableau en ordre inverse

Commentaire de coockiesch le 13/06/2006 09:09:08

Héhé, malalam fan d'escalade?
A part ca ce qui serait intéressant c'est de regrouper dans une même source plusieurs méthodes de tri... :)

@++

R@f

Commentaire de xque19 le 13/06/2006 10:25:06

Salut,

Moi personnellement, je n'arrive pas à voir où se trouve le côté récursif de cette fonction, je n'ai jamais eu à utiliser la recusivité en php mais bon si c'est le même principe de mise en oeuvre qu'ailleur, il ne devrait pas y avoir de boucle itérative "while" dans la fonction isort, et je ne vois pas non plus d'appels imbriqué, enfin peut-être que je me trompe.

++

Commentaire de TheSin le 13/06/2006 13:35:05

Oui, je suis d'accord avec toi xque19.
Il y a bien une boucle itérative While, mais aucune récursivité.
On se tromperait ?

Commentaire de Konkerouf le 26/10/2006 23:53:27

Mmmmh perso ce code me dérange pour plusieurs raisons:

-Il n'y a aucune récursivité la dedans. Tu crois qu'une boucle imbriquée dans une boucle est de la récursivité et tu te trompes. Une fonction récursive est une fonction qui s'appelle elle-même (pour justement éviter d'utiliser une boucle). Complètement inutile dans le cas d'un tri de tableau. La récursivité est très souvent une mauvaise solution. Ce sont des appels dans la pile ce qui coute cher en temps. Il n'y a que certains cas ou c'est plus avantageux de les utiliser et ce n'est surement pas le cas d'un tri de tableau (je pense aux opérations sur les arbres par exemple).

-Tu devrais mieux nommer tes variables. Le fait de les appeler $i et $j rend ton code assez incompréhensible, surtout pour un débutant. N'oublie pas que lire le code de quelqu'un d'autre est quelque chose d'assez lourd et de plutot compliqué quand on débute (meme si le code est simple).

-J'aime pas du tout cet algo en lui même. Pourquoi vouloir en "inventer" un nouveau alors que des algos très performant existe déja? (exemple: tri-bulle). Autant cela peut être nécessaire lors d'écriture de méthodes (ou fonctions, mais pourquoi faire du procédural quand on a la possibilité de faire de l'objet?) métiers, autant un algo de tri de tableau ça ne l'est pas.

Commentaire de anouartepdr le 03/04/2007 08:35:08

la fonction permet également de tier des mots ou quoi?

Commentaire de PaDa le 03/04/2007 10:53:11

Teste, tu verras bien ;o)

Commentaire de DarkM60 le 03/04/2007 12:53:54

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 !

Commentaire de zoukozouko le 12/04/2007 13:58:59

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???

Commentaire de PaDa le 12/04/2007 15:26:30

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)

Commentaire de zoukozouko le 12/04/2007 17:09:02

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!!!

Ajouter un commentaire

Discussions en rapport avec ce code source dans le forum

Trier un tableau selon 2 critères [ par tombal ] J'aimerais trier un tableau de requete mysql selon 2 critèresJe voudrais qu'il le tri dabord par ordre decroissant selon le nombre de points (le score Tri de fichiers par date [ par Clem ] Comment trier dans l'orde du plus nouveau au plus vieux, des dossiers ?J'ai trouvé pour afficher les dossiers :<?$rep=opendir('.');while ($file = r Tri d'IP... [ par echo200 ] Bonjour,En php, est-il possible de "trier" les ip authorisés à visitter un site web (définis selon nos critères), et d'éventuellement bannire les impo tri tableau 2 dimensions [ par lebobby ] Bonjour je voudrais savoir comment je pourrais faire pour trier ce tableau :$tab[0]=array("i"=>"23", "c" => "rge", "date" =>'2002-08-03 12:00 Insertion d'image dynamique [ par Licorne974 ] je souhaiterais savoir si il y a un petit script php par là !qui permettrais dans la saisie d'un formulaire d'insérer 2 photos qui se trouve sur mon d Ordre de tri ??! [ par benxen ] Bonjour,Tout juste debutant en php, je viens de recuperer un script permettant de lister toutes les images d'un repertoire afin de mettre leur nom dan insertion fichier dans page courante [ par crystel ] Bj,j'ai un formulaire avec 3 checkbox. Selon la checkbox cochée,je voudrais insérer le contenu d'un fichier texte différent en dessous du formulaire.. insertion texte [ par MasterJmC ] Salut est ce que quelqu'un pourrait me dire comment faire pour insérer des caractères dans un champ texte de formulaire à partir d'une image ou d'un b Insertion d'une nouvelle news au dessus de la précédente [ par 120385 ] Voilà j'ai petit problème :pJ'ai essayé de concevoir un système de news. il fonctionne a peu près, mais à chaque fois que je poste une news, elle s'af trier un resultat (requete mysql) par un champs choisi par lutilisateur [ par ricoux1 ] Comme vous allez vous en apercevoir je suis debutant en php et mysq, j'ai cree ma base de donnees, j'affiche les tables que je selectionne en cochant