IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Les meilleures sources algorithmes

Les meilleures sources algorithmesConsultez toutes les sources

Nombre d'auteurs : 1, nombre de sources : 15, dernière mise à jour : 4 janvier 2007 

 
OuvrirSommaireTris

Entrée :

 
Sélectionnez
T : tableau de nombre indexé de 1 à n

Sortie :

 
Sélectionnez
T trié

Pseudo-Code :

Fonction principale :

 
Sélectionnez
POUR i de 2 à n FAIRE
    INSERE( T , i-1, T[i] )
FIN POUR

Fonction INSERE(T, k , val )

 
Sélectionnez
i <- k
TANT QUE i > 0 et T[i] > val
    T[i+1] <- T[i]
    i <- i - 1
FIN TANT QUE
T[i+1] <- val

Complexité :

 
Sélectionnez
O(n^2)
Créé le 17 août 2006  par Romuald Perrot

Entrée :

 
Sélectionnez
T : Tableau de nombre indexé de 1 à n

Sortie :

 
Sélectionnez
T Trié

Pseudo-Code :

Fonction Principale :

 
Sélectionnez
POUR i de 1 à n-1 FAIRE
    ECHANGER( T , i , MINI(T,i,n) )
FIN POUR

Fonction MINI(T,i,n) :

 
Sélectionnez
min <- T[i]
 
POUR k de i+1 à n FAIRE
    SI T[k] < min ALORS
        min <- T[k]
    FIN SI
FIN POUR
 
RENVOYER min

Fonction Echanger( T , i , j ) :

 
Sélectionnez
temp <- T[i]
T[i] <- T[j]
T[j] <- temp

Complexité :

 
Sélectionnez
O(n^2)
Créé le 17 août 2006  par Romuald Perrot

Entrée :

 
Sélectionnez
T : Tableau à trier, indexé de 1 à n
d : entier, indice du début de la portion à trier.
f : entier, indice de la fin de la portion à trier.

Sortie :

 
Sélectionnez
T trié.

Pseudo-Code :

Fonction Principale : TRI( T , d , f )

 
Sélectionnez
SI d < f ALORS
    q <- (d+f) / 2
    TRI( T , d , q )
    TRI( T , q + 1 , f )
    T = FUSION( T[d..q], T[q+1..f])
FIN SI

Fonction FUSION( T1 , T2 )

 
Sélectionnez
i <- indice du début de T1
n <- indice de fin de T1
j <- indice du début de T2
m <- indice de fin de T2
k <- 1
 
TANT QUE i <= n et j <= m FAIRE
    SI T1[i] < T2[j] ALORS
        T[k] <- T1[i]
        k <- k+1
        i <- i+1
    SINON
        T[k] <- T2[j]
        k <- k+1
        j <- j+1
    FIN SI
FIN TANT QUE
 
TANT QUE i <= n FAIRE
    T[k] <- T1[i]
    k <- k+1
    i <- i+1
FIN TANT QUE
 
TANT QUE j <= m FAIRE
    T[k] <- T2[j]
    k <- k+1
    j <- j+1
FIN TANT QUE
 
RENVOYER T

Complexité :

 
Sélectionnez
O(n ln n)
Créé le 17 août 2006  par Romuald Perrot

Entrée :

 
Sélectionnez
T : Tableau de nombre indexé de 1 à n
d : entier, indice du début du tri (au premier appel d = 1)
f : entier, indice de la fin du tri (au premier appel f = n)

Sortie :

 
Sélectionnez
T trié

Pseudo-Code :

fonction principale : TRI( T , d , f )

 
Sélectionnez
SI d < f ALORS
    q <- PARTITION( T , d , f )
    TRI( T , d , q-1 )
    TRI( T , q+1 , f )
FIN SI

fonction PARTITION( T , d , f )

 
Sélectionnez
pivot <- T[f]
i <- d-1
POUR j de d à f - 1 FAIRE
    SI T[j] <= pivot ALORS
        i <- i+1
        ECHANGER( T , i , j )
    FIN SI
FIN POUR
ECHANGER( T , i+1 , f )
 
RENVOYER i+1

Fonction ECHANGER( T, i , j )

 
Sélectionnez
temp <- T[i]
T[i] <- T[j]
T[j] <- temp

Complexité :

 
Sélectionnez
-> Pire : O(n^2)
-> Moyen : O(n ln n )
-> Meilleur : O(n ln n)
Créé le 17 août 2006  par Romuald Perrot

Entrée :

 
Sélectionnez
T : Tableau à trier, indexé de 1 à n

Sortie :

 
Sélectionnez
T trié.

Pseudo-Code :

 
Sélectionnez
POUR i de 1 à N FAIRE 
    POUR k de 1 à N - i FAIRE 
	    SI T[k] > T[k+1] ALORS 
		    T[k] <-> T[k+1] 
	    FIN SI 
	FIN POUR 
FIN POUR

Complexité :

 
Sélectionnez
O(n^2)
Créé le 17 décembre 2006  par Romuald Perrot

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2006 Developpez Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.