Les Algorithmes

I)Introduction

a)Définition :

Un algorithme est une suite d’opérations que l’on met en place pour résoudre un problème ou bien une classe de problèmes, il est ainsi présent dans le domaine de l’algorithmique.

Il est utilisé pour résoudre chaque problème lui faisant face, en revanche un algorithme sera plus efficace si il est utilisé sur une machine étant composé de meilleurs composant( Mémoire vive, CPU, l’alimentation).

On utilisera un des langages de programmations pour l’exprimer(Perl, Python, Java, C++, CAML, ….).

b)Exemples d’algorithme :

Comme on peut le voir ci-dessus, on a un exemple d’un algorithme, exprimé ici pour découpé un polygone quelconque en triangles.

C’est bien beau tout ça, alors comment un algorithme est codé ?

II)Différents Tri

a)Tri par insertion

On peut en déduire ci-dessous, un algorithme permettant de faire un tri par insertions :

VARIABLE
t : tableau d'entiers
i : nombre entier
j : nombre entier
k : nombre entier
DEBUT
j←2
tant que j<=longueur(t):   //boucle 1
  i←j-1
  k←t[j]
  tant que i>0 et que t[i]>k:   //boucle 2
    t[i+1]←t[i]
    i←i-1
  fin tant que
  t[i+1]←k
  j←j+1
fin tant que
FIN

Voici un code représentant un tri par insertion, code que l’on utilise pour mélanger essentiellement des cartes à jouer malgré la lenteur de ce code il reste le plus efficace comparé au tri rapide.

Si on veut trier un paquet de cartes sous forme d’un codage, ici python on reproduit le code ci-dessous :

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

Tout d’abord, on définit la fonction « tri insertion »(tableau), on lui demande de chercher pour i dans un entier 1 et la longueur du tableau, après cela les éléments du tableau vont se décaler pour trouver leurs place en analysant chacun des éléments initialement présents. Enfin, une fois l’analyse terminé en ayant trouvé le bon élément a remplacé, l’élément en mouvement prendra la place de l’intru se situant dans le mauvaise emplacement.

Une fois le tri terminé avec chacun des éléments présent, on aura un jeu de carte parfaitement trié :

b)Tri par sélection

On utilise le tri par sélection pour aller chercher le plus petit élément du vecteur pour le placer en premier , pour ensuite repartir du second élément et aller chercher le plus petit élément et ainsi de suite.

Ainsi on veut Trié ce jeu de carte :

On va donc coder un algorithme, permettant de réaliser notre but :

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

Ainsi, on cherche dans dans le tableau différentes valeurs, recherche effectué lors du démarrage du programme, voilà pourquoi on utilise « en_cours » dans les lignes de codes.