12
décembre
2014
Collection d’algorithmes
décembre
2014
Un article de Walik
Collectionner les timbres c’est mal, collectionner les algorithmes c’est bien :
Trie à bulle
procédure tri_bulle(tableau T, entier n)
répéter
échange_effectué = faux
pour j de 0 à n - 2
si T[j] > T[j + 1], alors
échanger T[j] et T[j + 1]
échange_effectué = vrai
fin si
fin pour
tant que échange_effectué = vrai
fin procédure
répéter
échange_effectué = faux
pour j de 0 à n - 2
si T[j] > T[j + 1], alors
échanger T[j] et T[j + 1]
échange_effectué = vrai
fin si
fin pour
tant que échange_effectué = vrai
fin procédure
Trie fusion
fonction trier(p, n)
Q:= n/2 (division entière)
P:= n-Q
si P >= 2
q:= trier(p, P)
si Q >= 2 trier(q, Q)
sinon
q:= p.suivant
fin
q:= fusionner(p, P, q, Q)
renvoyer q
fin
fonction fusionner(p, P, q, Q)
répéter indéfiniment
si valeur(p.suivant) > valeur(q.suivant)
déplacer le maillon q.suivant après le maillon p
si Q = 1 quitter la boucle
Q:= Q-1
sinon
si P = 1
tant que Q >= 1
q:= q.suivant
Q:= Q-1
fin
quitter la boucle
fin
P:= P-1
fin
p:= p.suivant
fin
renvoyer q
fin
Q:= n/2 (division entière)
P:= n-Q
si P >= 2
q:= trier(p, P)
si Q >= 2 trier(q, Q)
sinon
q:= p.suivant
fin
q:= fusionner(p, P, q, Q)
renvoyer q
fin
fonction fusionner(p, P, q, Q)
répéter indéfiniment
si valeur(p.suivant) > valeur(q.suivant)
déplacer le maillon q.suivant après le maillon p
si Q = 1 quitter la boucle
Q:= Q-1
sinon
si P = 1
tant que Q >= 1
q:= q.suivant
Q:= Q-1
fin
quitter la boucle
fin
P:= P-1
fin
p:= p.suivant
fin
renvoyer q
fin
Trie rapide
partitionner(tableau T, premier, dernier, pivot)
échanger T[pivot] et T[dernier]
j := premier
pour i de premier à dernier - 1
si T[i] <= T[dernier] alors
échanger T[i] et T[j]
j := j + 1
échanger T[dernier] et T[j]
renvoyer j
tri_rapide(tableau t, entier premier, entier dernier)
début
si premier < dernier alors
pivot := choix_pivot(t,premier,dernier)
pivot := partitionner(t,premier, dernier,pivot)
tri_rapide(t,premier,pivot-1)
tri_rapide(t,pivot+1,dernier)
fin si
fin
échanger T[pivot] et T[dernier]
j := premier
pour i de premier à dernier - 1
si T[i] <= T[dernier] alors
échanger T[i] et T[j]
j := j + 1
échanger T[dernier] et T[j]
renvoyer j
tri_rapide(tableau t, entier premier, entier dernier)
début
si premier < dernier alors
pivot := choix_pivot(t,premier,dernier)
pivot := partitionner(t,premier, dernier,pivot)
tri_rapide(t,premier,pivot-1)
tri_rapide(t,pivot+1,dernier)
fin si
fin
Trie par tas
fonction tamiser(arbre,nœud,n):
{descend arbre[nœud] à sa place, sans dépasser l'indice n}
k:=nœud
j:=2k
tant que j<=n
si j<n et arbre[j]<arbre[j+1]
j:=j+1
fin si
si arbre[k]<arbre[j]
échanger arbre[k] et arbre[j]
k:=j
j:=2k
sinon
terminer
fin si
fin tant que
fin fonction
fonction tri_par_tas(arbre,longueur):
pour i:=longueur/2 a 1
tamiser(arbre,i,longueur)
fin pour
pour i:=longueur a 2
échanger arbre[i] et arbre[1]
tamiser(arbre,1,i-1)
fin pour
fin fonction
{descend arbre[nœud] à sa place, sans dépasser l'indice n}
k:=nœud
j:=2k
tant que j<=n
si j<n et arbre[j]<arbre[j+1]
j:=j+1
fin si
si arbre[k]<arbre[j]
échanger arbre[k] et arbre[j]
k:=j
j:=2k
sinon
terminer
fin si
fin tant que
fin fonction
fonction tri_par_tas(arbre,longueur):
pour i:=longueur/2 a 1
tamiser(arbre,i,longueur)
fin pour
pour i:=longueur a 2
échanger arbre[i] et arbre[1]
tamiser(arbre,1,i-1)
fin pour
fin fonction
Recherche séquentielle
fonction recherche_seq(tableau T, entier n, r)
d = faux
pour i:=0 a n
Si T[i] = r
d = vrai
quitter la boucle
fin si
fin pour
si d = vrai
retourner i
sinon
retourner -1
fin si
fin fonction
d = faux
pour i:=0 a n
Si T[i] = r
d = vrai
quitter la boucle
fin si
fin pour
si d = vrai
retourner i
sinon
retourner -1
fin si
fin fonction
Recherche dichotomique
fonction recherche_dic(tableau T, entier n, r)
plage := n
indice := 0
t := -1
tant que plage > 0
si T[indice] = r
t := indice
quitter boucle
fin si
si indice = 0 et T[indice] > r
quitter boucle
fin si
plage /= 2
si T[indice] > r
indice +:= plage
sinon
indice -:= plage
fin si
retourner t
fin fonction
plage := n
indice := 0
t := -1
tant que plage > 0
si T[indice] = r
t := indice
quitter boucle
fin si
si indice = 0 et T[indice] > r
quitter boucle
fin si
plage /= 2
si T[indice] > r
indice +:= plage
sinon
indice -:= plage
fin si
retourner t
fin fonction
Pagination
fonction pagination(tableau T, entier numero_page, entier lignes_par_page)
taille_tableau := taille(taille_tableau)
nb_page := taille_tableau % lignes_par_page
si numero_page > a nb_page
retourner erreur
fin si
si numero_page := nb_page
reste_lignes = taille_tableau - nb_page * ligne_par_page
sinon
reste_lignes := lignes_par_page
fin si
debut := numero_page * lignes_par_page
fin := debut + reste_lignes
retourner sous_tableau(tableau, debut, fin)
fin fonction
taille_tableau := taille(taille_tableau)
nb_page := taille_tableau % lignes_par_page
si numero_page > a nb_page
retourner erreur
fin si
si numero_page := nb_page
reste_lignes = taille_tableau - nb_page * ligne_par_page
sinon
reste_lignes := lignes_par_page
fin si
debut := numero_page * lignes_par_page
fin := debut + reste_lignes
retourner sous_tableau(tableau, debut, fin)
fin fonction
Affichage d’arborescense
fonction affiche_arbo(entier id)
entier id_fils = base_de_donnee(id)
chaine nom = base_de_donnee(id)
ecrire(nom)
si id_fils != NULL
affiche_arbo(id)
fin si
fin fonction
entier id_fils = base_de_donnee(id)
chaine nom = base_de_donnee(id)
ecrire(nom)
si id_fils != NULL
affiche_arbo(id)
fin si
fin fonction
Préférence
fonction Lecture(chanson)
playList[chanson] += 1
fin fonction
fonction preference()
retourner tri_fusion(playList)
fin fonction
playList[chanson] += 1
fin fonction
fonction preference()
retourner tri_fusion(playList)
fin fonction
Analyse de performance matérielle
constante temps_reference = a
constante repetition = b
t1 = timestamp
pour i:=0 a repetition
tache()
fin pour
t2 = timestamp
t = t2-t1
ratio = 1 / t / temps_reference * 100
ecrire ratio
constante repetition = b
t1 = timestamp
pour i:=0 a repetition
tache()
fin pour
t2 = timestamp
t = t2-t1
ratio = 1 / t / temps_reference * 100
ecrire ratio
Range détection une seule comparaison
fonction inRange(min, max, s)
retourner (s-(max+1)) * (s-(min-1)) < 0
fin fonction
retourner (s-(max+1)) * (s-(min-1)) < 0
fin fonction
Un puzzle
fonction creer_puzzle(tableau p)
pour i:= 0 a taille(p)
p[i][position_initiale] = i
p[i][position_actuelle] = i
fin pour
retourner p
fonction melange_puzzle(tableau p)
t = taille(p)
pour i:= 0 a t
t_hasard[i] = i
fin pour
tt = t
pour i:=0 a t
h = hasard(tt)
val = t_hasard[h]
extraire(t_hasard[h])
tt = tt - 1
p[i][position_actuelle] = val
fin pour
desordre = t
retourner p, desordre
fin fonction
fonction bouger(tableau p, entier indice, position, desordre)
p[indice][postion_actuelle] = position
si position == p[indice][position_initiale] alors desordre = desordre -1
retourner p, desordre
pour i:= 0 a taille(p)
p[i][position_initiale] = i
p[i][position_actuelle] = i
fin pour
retourner p
fonction melange_puzzle(tableau p)
t = taille(p)
pour i:= 0 a t
t_hasard[i] = i
fin pour
tt = t
pour i:=0 a t
h = hasard(tt)
val = t_hasard[h]
extraire(t_hasard[h])
tt = tt - 1
p[i][position_actuelle] = val
fin pour
desordre = t
retourner p, desordre
fin fonction
fonction bouger(tableau p, entier indice, position, desordre)
p[indice][postion_actuelle] = position
si position == p[indice][position_initiale] alors desordre = desordre -1
retourner p, desordre
Mots-clés : algorithme, algorithmique