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

Ce site au démarrage

begin process at 2012 02 12 20:04:38

Accueil Codes Tutoriels Forum Livres Emploi Services Connexion

Trouver un code source :

dans

[ Dernières recherches ]

Accueil >

TRI PAR INSERTION

Information sur la source

Note :
Aucune note

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 :11 941

Auteur : DarkM60

Ecrire un message privé

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

SCRIPT D'ENVOI DE SMS DEPUIS SFR

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

EXEMPLE D'APPLICATION DE L'ALGORITHME DE DIJKSTRA EN PHP par philtr8

CLEF POUR EAN 13 ET 14 par RaftY

FONCTION DE CALCUL DU NOMBRE DE DUEL UNIQUE POUR UN NOMBRE N... par mtrix000

TRIANGLE DE PASCAL ET SON ÉQUATION par vendeeHdLR89

CONVERTISSEUR LAMBERT2 ÉTENDU EN COORDONNÉE GÉOGRAPHIQUE (LO... par varfendell

Toutes les sources de la catégorie Maths & Algorithmes

Sources en rapport avec celle ci

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

PHP_PUZZLE par coucou747

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

Nos sponsors

Derniers Blogs

[WP7] DYNAMICALLY CHANGE STARTUP PAGE par KooKiz

SESSION SILVERLIGHT 5 3D : SLIDES ET DEMOS par Groc

[TECHDAYS 2012] SESSION WEBMATRIX 2 : LE COUTEAU SUISSE GRATUIT POUR VOS DéVELOPPEMENTS WEB - SLIDES par gpommier

[SHAREPOINT] LES SESSIONS TECHDAYS 2012. par Patrick Guimonet

TECHDAYS PARIS 2012 : SESSION PLEINIèRE JOUR 3 par ROMELARD Fabrice

Forum

RE : AFFICHAGE DE DONNéES par NHenry

AFFICHAGE DE DONNéES par tanoh

RE : SONDAGE.. par phpAnonyme

RE : SONDAGE.. par TychoBrahe

RE : LIEN VERS UN INCLUDE SANS RECHARGER LA PAGE AVEC AJAX par stealon

Côté IT

Offres d'emploi

Formations Video

Appels d'offres

Passerelle Pericles sur site Joomla 17
Budget : 499€
Infogerance Serveur Debian Linux
Budget : 2 400€
Developpeur applications iphone - ipad - android
Budget : 800€

Logiciels

Tribler (2012)
TRIBLER (2012)

Tribler est un client pair à pair (P2P/Peer-to-Peer) open source avec la capacité de regarder des...

Cliquez pour télécharger Tribler
OneSwarm (2012)
ONESWARM (2012)

Le peer-to-peer qui protège votre vie privée, c'est OneSwarm. Ce logiciel de peer-to-peer crypté...

Cliquez pour télécharger OneSwarm
PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V8.4)
PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V8.4)

PONAMEDIA TV DEVIENS HELLLOOO FLASH LA TV SUR VOTRE ORDINATEUR. Toute une plateforme Multi...

Cliquez pour télécharger PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO
Academy System (17.2.1.0)
ACADEMY SYSTEM (17.2.1.0)

Logiciel de gestion des établissements. - élèves/étudiants (inscription, dossier, absence...) -...

Cliquez pour télécharger Academy System
Easy-Planning (1.0.0.1)
EASY-PLANNING (1.0.0.1)

Basé sur les mêmes principes que MyPlanning, Easy-Planning permet de créer des plannings sous la ...

Cliquez pour télécharger Easy-Planning