Introduction
Trier des objets est à la fois un problème fondamental de l'algorithmique, comme étape de prétraitement d'algorithmes plus complexes ou pour ordonner des structures de données (à quoi servirait un annuaire non trié ?)... et une bonne illustration de différents paradigmes de programmation (diviser pour régner)
Déterminer si un tableau est trié ?? |
Première proposition :
FONCTION est_trié (T : TABL N : ENTIER) : BOOLEEN
VAR i : ENTIER
DEBUT
i 1
TANTQUE (i < N) ET (T[i] ≤ T[i+1]))
FAIRE ii+1
FINTANTQUE
RETOURNER (i=N)
FIN
Remarque :
Il y a un problème quand i vaut N : on évalue la condition i<N ET (T[i] ≤ T[i+1]) or la case T[N+1] n'existe pas.
La première partie (i<N) de la condition renvoie faux --> la condition va renvoyer aussi faux ; Mais certains langages évalue quand même la deuxième condition (ce n'est pas le cas du C++) : Don à éviter de l'appliquer en algorithmique.
Deuxième proposition :
On utilise une variable booléenne :
FONCTION est_trié (T : TABL, N : ENTIER) : BOOLEEN
VAR i : ENTIER
TRIE : BOOLEEN
DEBUT
i1
TRIEvrai
TANTQUE ((i<N) ET TRIE)
FAIRE
SI T[i]≤T[i+1]
ALORS ii+1
SINON TRIE faux
FINSI
FINTANTQUE
RETOURNER( TRIE)
FIN