D'autre part tous les éléments du sous-vecteur V[1..i] sont inférieurs ou égaux à l'élément V[i+1].         V[1..i] non traité, V[1..i] <= V[i+1], V[i+1..N] Trié(V[1] non traité, V[1]<= V[2], V[2..N] trié) donc V[1..N] triéPour augmenter le sous-vecteur V[i+1..n] d'un élément, il suffit de chercher le plus grand élément contenu dans le sous-vecteur V[1..i] et de placer cet élément en position i.Après avoir traité n-i (1 <= i < N) éléments du vecteur.         V[1..i] non traité                              V[i+1..N] Trié  1                                           i                                             NOn peut donc considérer le vecteur V comme la concaténation de deux sous-vecteurs : le sous-vecteur V[1..i] dont les éléments n'ont pas encore été triés, et le sous vecteur V[i+1..N] dont les éléments sont triés. Paramètres en entrée : un tableau de N entiers et une valeur v; Paramètres en sortie : l'entier nb. VAR V : tableau[1..N] de réel N, i, j : entier AUX : réel. Vous pouvez continuer la lecture de nos cours en devenant un membre de la communauté d'OpenClassrooms. Plus l'on va vers le haut, plus le nombre d'opérations effectuées augmente et donc plus la quantité de mémoire ou le temps processeur nécessaire augmente. Enfin, nous étudierons la complexité de ces différents algorithmes de manière empirique en effectuant quelques mesures.Ce chapitre est davantage un chapitre d'algorithmique que de programmation. Elle est toutefois linéarithmique c'est-à-dire en Différentes variantes de ces algorithmes existent. Cette opération permet d'obtenir en fin du i                   SI V[j]>V[j+1] ALORS                     AUX ¬ V[j]                     V[j] ¬ V[j+1]                     V[j+1] ¬ AUXExécuter à la main cet algorithme avec les vecteurs suivants :                    SI (V[J+1] < V[j]) ALORS                            AUX¬V[J+1]                            V[J+1] ¬V[J]                            V[J] ¬ AUX                            atonpermuté¬vrai                   SI V[j]>V[j+1] ALORS                     AUX ¬ V[j]                     V[j] ¬ V[j+1]                     V[j+1] ¬ AUX La programmation modulaire IV : Héritage et dérivation

Il faut ensuite répéter cette manœuvre avec l'avant-dernière feuille, puis l'avant-avant-dernière feuille… Jusqu'à arriver à la deuxième (et oui, inutile d'échanger la racine avec elle-même, soyons logique). o_OEn effet. Il ne vous reste plus qu'à l'implémenter.Vous l'aurez deviné je l'espère, il nous faut une procédure tamiser, en plus de notre fonction Tri_tas. Le principe est simple mais rudement efficace (un peu moins que le tri rapide toutefois). Eh bien c'est simple, on la sort du paquet de cartes pour l'insérer à la bonne place dans la partie des cartes déjà triées. Pour trier notre arbre par tas, nous allons le tamiser en commençant, non pas par la racine de l'arbre, mais par les derniers nœuds (en commençant par la fin en quelque sorte). L'algorithme renvoie le rang (la valeur -1 est renvoyée lorsque l'élément Elt n'est pas présent dans le tableau t). Un cas particulier notable est k = n /2, qui correspond à la recherche de la médiane . Pour limiter les tests inutiles, nous commencerons par tamiser le 3, puis le 7 et enfin le 5. Je vous présente sur la figure suivante les résultats obtenus avec mon vieux PC.Avant même de comparer les performances de nos algorithmes, on peut remarquer une certaine irrégularité : des pics et des creux apparaissent et semblent (en général) avoir lieu pour tous les algorithmes. Les qualificatifs de «lent», «rapide», «pire» ou «meilleur» sont donc à prendre avec des pincettes, car certains peuvent être très nettement améliorés ou sont très utiles dans des cas particuliers.Par exemple, notre algorithme de tri fusion est un tri en place : nous n'avons pas créer de second tableau pour effectuer notre tri afin d'économiser la mémoire, denrée rare si l'on trie de très grands tableaux (plusieurs centaines de millions de cases). Un algorithme de tri est un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Plus on descend dans l'arbre plus les nombres sont petits, mais c'est pas trié pour autant ?! Tout cela ralentit les performances de l'ordinateur et peut même, pour des algorithmes mal ficelés, saturer la mémoire entraînant l'erreur D'où l'intérêt de pouvoir comparer la complexité de différents algorithmes pour ne conserver que les plus efficaces, voire même de prédire cette complexité.