Tri fusion - mergesort

Télécharger le projet
Commenter

Description

Tri par fusion - MergeSort
Prend un tableau et le sépare en 2. Ensuite prend chaque tableau et separe ceux-ci encore en 2. Jusqu'à ce qu'il ne reste qu'un seul élément.
Ensuite, avec chaque petit tableau de 1 on refait le gros tableau en comparant à chaque fois chaque élément.
Pour mieux comprendre, il vous faut un dessin ! Cherchez sur Google : tri fusion.
La complexité de cet algorithme est de O(n log n).

Ce script a été réalisé avec 2 autres coéquipiers en C, mais il a été transféré en PHP par Jean-Sébastien Goupil

Difficulté : Fonction Récursive
Compatible PHP4, PHP5

Source / Exemple : 


<?php
//////////////////////////////////////////////////////////////////////
// fusion.php
//--------------------------------------------------------------------
//
// Tri par fusion - MergeSort
// Prend un tableau et le sépare en 2. Ensuite prend chaque tableau
// et separe ceux-ci encore en 2. Jusqu'à ce qu'il ne reste qu'un seul
// élément.
// Ensuite, avec chaque petit tableau de 1 on refait le gros tableau
// en comparant à chaque fois chaque élément.
// Pour mieux comprendre, il vous faut un dessin ! Cherchez sur Google
// tri fusion.
// La complexité de cet algorithme est de O(n log n)
//
// Ce script a été réalisé avec 2 autres coéquipiers en C
// mais il a été transféré en PHP par Jean-Sébastien Goupil
//
//--------------------------------------------------------------------
// Revision History
// V1.00	23 aug	2004	Jean-Sebastien Goupil
//--------------------------------------------------------------------
// Copyright (C) Jean-Sebastien Goupil
// http://other.lookstrike.com/
//--------------------------------------------------------------------
//////////////////////////////////////////////////////////////////////
function triFusion ( &$tab ) {
	 if( count( $tab ) <= 1 ) return;
	 else {
		$tab1 = array();
		$tab2 = array();

		// Répartie les information dans 2 tableaux différent
		for( $i = 0; $i < count( $tab ); $i++) {
			if( $i < ( count( $tab ) ) / 2 )
				$tab1[] = $tab[ $i ];
			else
				$tab2[] = $tab[ $i ];
		}

		// Appel la fonction tri récursivement
		triFusion( $tab1 );
		triFusion( $tab2 );

		// Fusionne les petits tableaux en plus grand
		fusionner( $tab1, $tab2, $tab );
	}
}

function fusionner ( $tab1, $tab2, &$tab ) {
	$i = 0;
	$i1 = $i2 = 0;
	// Fusionne les petits tableaux dans le plus grand
	while( $i1 < count( $tab1 ) && $i2 < count( $tab2 ) ) {
		if( $tab1[ $i1 ] < $tab2[ $i2 ] ) // On compare ici
			$tab[ $i ] = $tab1[ $i1++ ];
		else
			$tab[ $i ] = $tab2[ $i2++ ];
		$i++;
	}

	// S'il reste des éléments dans un des 2 tableaux mais pas dans l'autre
	while( $i1 < count( $tab1 ) ) {
		$tab[ $i ] = $tab1[ $i1++ ];
		$i++;
	}
	while( $i2 < count( $tab2 ) ) {
		$tab[ $i ] = $tab2[ $i2++ ];
		$i++;
	}
}

$a = split(' ','Voici un tri par fusion !');
triFusion ( $a );
print_r($a);
?>

Conclusion :


Pour ceux qui disent que ca existe déjà en fonction directement en PHP eh bien tant mieux pour vous utilisez-la ! mais avec celle-ci, vous pouvez personnaliser par exemple plusieurs tableaux et la modifier à votre guise !

La ligne :
if( $tab1[ $i1 ] < $tab2[ $i2 ] ) // On compare ici
Vous pouvez la modifier et utiliser un strcmp ou tout autre de ressemblance :)
Mais PHP est intelligent donc < fonctionne aussi pour les chaines de caractères !
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (cs_GRenard)