Quelques algorithmes simples

Un algorithme est une suite finie et non ambiguë d’instructions et d’opérations permettant de résoudre un type de problèmes. Il est dit correct lorsque, pour chaque instance du problème, il se termine en produisant la bonne sortie, c’est-à-dire qu’il résout le problème posé.

2) Tri par insertion ,par sélection

Le tri par insertion : l’algorithme va chercher une valeur inférieur à la dernière en analysant la liste , des qu’il la trouver

Puis il va la prendre , pour la ramener en arrière jusqu’à trouver une valeur supérieur à celle sélectionner

Le tri par sélection : Il va prendre la 1er valeur , est il va analyser la liste jusqu’à trouver la valeur la plus inférieur à celle sélectionner ici la valeur la plus inférieur à 6 c’est 2 donc il finis d’analyser si il trouve pas de valeurs encore plus petite .

Les deux valeurs s’échange ! puis il continue avec les autres valeurs de la liste une par une . Attention s’il ne trouve pas de valeurs inférieur à celle sélectionner il la laisse et passe a la valeur suivante !

Voici un exemple type insertion puis sélection :

Par Insertion :

def tri_insertion(tableau):
    for i in range(1,len(tableau)):
        en_cours = tableau[i]
        j = i
        #décalage des éléments du tableau }
        while j>0 and tableau[j-1]>en_cours:
            tableau[j]=tableau[j-1]
            j = j-1
        #on insère l'élément à sa place
        tableau[j]=en_cours

Traduction en Pseudo code pour mieux comprendre :

ROCEDURE tri_Selection ( Tableau a[1:n])
    POUR i VARIANT DE 1 A n - 1 FAIRE
        TROUVER [j] LE PLUS PETIT ELEMENT DE [i + 1:n];
        ECHANGER [j] ET [i];
FIN PROCEDURE;

Par Sélection :

def tri_selection(tableau):
    nb = len(tableau)
    for en_cours in range(0,nb):    
        plus_petit = en_cours
        for j in range(en_cours+1,nb) :
            if tableau[j] < tableau[plus_petit] :
                plus_petit = j
        if min is not en_cours :
            temp = tableau[en_cours]
            tableau[en_cours] = tableau[plus_petit]
            tableau[plus_petit] = temp

Traduction Pseudo Code pour mieux comprendre :

ROCEDURE tri_Selection ( Tableau a[1:n])
    POUR i VARIANT DE 1 A n - 1 FAIRE
        TROUVER [j] LE PLUS PETIT ELEMENT DE [i + 1:n];
        ECHANGER [j] ET [i];
FIN PROCEDURE;

Source : http://lwh.free.fr/pages/algo/tri/tri_selection.html

http://lwh.free.fr/pages/algo/tri/tri_insertion.html