Tri par tas
Principe
Pour bien comprendre le tri par tas il sera utile de connaitre un minimum le concept des arbres.
A partir des données, on va crée un arbre binaire tel qu'au sommet de cet arbre se trouve toujours l'élément le plus petit de tout l'arbre. Une fois l'arbre crée, il ne restera plus qu'à retirer tout les élément un à un en faisant remonter a chaque fois l'élément le plus petit des sous arbres.
Algorithme
noeud: -valeur -FilsGauche (un autre noeud) -FilsDroit (un autre noeud) -CardinalGauche (nombre d'élément dans Fils Gauche) -CardinalDroit (nombre d'élément dans Fils Droit)
Fonction Ajout (T, x) retourne Tas Parametre (e/s) t: tas x: entier DEBUT si Vide (T) alors retourne CreeArbre (x) si (x < Valeur(T)) alors inverser (x, Valeur (T)) si ( CardinalGauche (T) < CardinalDroit (T) ) alors CardinalGauche(T)<-CardinalGauche(T)+1 FilsGauche(T)<-Ajout (FilsGauche(T), x) sinon CardinalDroit(T)<-CardinalDroit(T)+1 FilsDroit(T)<-Ajout (FilsDroit(T), x) retourne T FIN
Fonction retireRacine (T) retourne entier Parametre (e/s) T: Tas variable: val: entier DEBUT val<-valeur(T) si (CardinalGauche (T) = CardinalDroit(T) = 0 )alors T<-vide retourne val si nonVide (FilsGauche(T)) alors si nonVide (FilsDroit(T)) alors si (valeur(FilsGauche(T)) < valeur(FilsDroit(T))) alors CardinalGauche(T) <- CardinalGauche(T) - 1 valeur (T) <- retireRacine (FilsGauche(T)) sinon CardinalDroit(T) <- CardinalDroit(T) - 1 valeur (T) <- retireRacine (FilsDroit(T)) sinon CardinalGauche(T) <- CardinalGauche(T) - 1 valeur (T) <- retireRacine (FilsGauche(T)) sinon CardinalGauche(T) <- CardinalGauche(T) - 1 valeur (T) <- retireRacine (FilsDroit(T)) retourne val FIN
Complexite
La compléxité du tri par tas est de O(N*log2(N)). Ce n'est pas très compliqué à calculer. le retrait dans le tas est en N*log2(N) car l'arbre est de hauteur log2(N) (l'arbre est équilibre) et que l'on met à jour un noeud par niveau dans l'arbre et ce pour tout les neoud (N)