en ce beau dimanche matin (je vais me coucher bientôt) je vous laisse en compagnie de cette petite vidéo ….
Alors la grande question que ça fait une semaine que je me la pose, les vidéo, ca chie ou pas ? J’ai comme l’impression que y’a pas de débit…
alors, on choisit un bon master et tout et puis cours d’info, c++. Cool, enfin on va s’occuper. On trouve les sujet de TP et on peut s’exercer à la maison. C’est pas mal, ça permet d’aller plus vite en codant (c’est en forgeant qu’on devient …).
Bref, ci dessous un extrait du tp (le verso de la feuille pour être précis), le prof en tp demande l’un des tri suivant :
le tri bulle
Cet algorithme est relativement connu, bien qu’il soit rarement efficace (en termes de temps de calcul, le tri est néanmoins correct, bien évidement). Il consiste à balayer tout le tableau, en comparant les éléments adjacents et les échangeant s’ils ne sont pas dans le bon ordre. Plus précisément : on parcourt tout le tableau. dès qu’un élément est plus grand que son suivant, on échange les deux. Arrivé au bout du tableau, il faut recommencer. En effet, un seul passage ne déplacera un élément donné que d’une position. Mais en répétant le processus jusqu’à ce plus aucun échange ne soit nécessaire, le tableau sera trié. Il vous faudra donc utiliser un “truc” pour vérifier s’il y a eu un changement : au début, on met une variable à 0. A chaque changement, on la met à 1. Si l’on arrive à la fin du tableau et que la variable est restée à 0, on n’a donc plus rien à échanger, le tableau est trié. Je vous conseille de prévoir une fonction qui échange deux températures adjacentes.
le tri par insertion
On prend un élément après l’autre, dans l’ordre initial, et on le place correctement dans les éléments précédents déjà triés, comme on le fait lorsque l’on classe ses cartes à jouer après la donne. Plus précisément : la première (seule) est évidement triée. On regarde la seconde. Si elle est plus grande, on la laisse, sinon on la place devant l’autre. Puis on regarde la troisième, et on va la placer au bon endroit dans les deux précédentes (en premier, au milieu ou laissée à la fin). Puis on teste la quatrième, etc… jusqu’à avoir complètement balayé le tableau. Je vous conseille de prévoir une fonction qui permet d’avancer une carte depuis une position i vers une position j (j < i), en décalant toutes celles entre j et i d’un cran.
le tri par sélection
On recherche l’élément le plus petit. Il faut donc le placer en premier. Or cette position est déjà occupée, on se propose donc d’échanger les deux éléments. Il ne reste plus qu’à répéter l’opération N fois (N étant la taille du tableau). C’est à dire qu’on recherche ensuite le plus petit dans ceux qui restent (N-1), on le met en seconde position, on recommence pour chercher le troisième, et ainsi de suite jusqu’à l’avant dernier (le dernier sera automatiquement classé). Je vous conseille de prévoir une fonction qui permet de chercher la position (et pas la valeur) du plus petit élément du tableau, à partir d’une position donnée en argument. Une autre qui permet d’échanger deux températures (dont on donne la position en argument).
le tri shell
C’est une amélioration du tri par insertion : au lieu d’effectuer une rotation de tous les éléments entre la position initiale et finale (ou du moins meilleure) d’un élément, on peut faire des rotations par pas de P, ce qui rendra le fichier presque trié (chaque élément sera à moins de P positions de sa position exacte). On répète ce tri pour P diminuant jusqu’à 1. Une suite possible pour P est de finir par 1, les pas précédents étant de 4, 13, 40, 121, 364, 1093… (Pi=3*Pi-1 +1). D’autres suites sont évidement possibles, à condition de prendre des valeurs qui ne soient pas multiples entre elles (pour ne pas toujours traiter les mêmes éléments et laisser de côté les autres, par exemple les puissances successives de 2 ne traiteraient que les positions paires, sauf au dernier passage.
le tri rapide (Quick Sort)
Ce tri est récursif. L’idée est de prendre une valeur du tableau (appelée pivot), de mettre toutes les valeurs plus petites devant (sans les trier, bien sûr), toutes les plus grandes derrière. Il ne reste plus qu’à trier les deux demi tableaux. On utilise pour cela la récursivité, c’est à dire qu’on utilise la même méthode pour traiter chaque demi tableau, et ce jusqu’à ce que la taille soit petite pour être évidente à trier (taille 1). En pratique, on cherche à trier la partie du tableau délimitée par les indices gauche et droite. On choisit une valeur de ce sous-tableau (une valeur médiane serait idéale, mais sa recherche ralentit plus le tri que de prendre aléatoirement une valeur, par exemple la dernière), que l’on appelle pivot. Puis on cherche la position définitive de ce pivot, c’est à dire qu’on effectue des déplacements de valeurs de telle sorte que tous les éléments avant le pivot soient plus petits que lui, et que toutes celles après lui soient supérieures, mais sans chercher à les classer pour accélérer le processus. Puis on rappelle récursivement le tri de la partie avant le pivot, et de celle après le pivot. On arrête la récursivité sur les parties à un seul élément, qui est donc nécessairement triée.
le tri par création
Lorsqu’il est nécessaire de disposer simultanément du tableau initial et du tableau trié, on peut recopier le tableau initial puis effectuer un tri sur la copie, ou adapter un des algorithmes précédents. Par exemple, à partir du tri par sélection, l’algorithme consiste à rechercher l’élément le plus petit, le copier en première position du tableau final, rechercher le suivant, le placer en seconde position, etc… En cas d’éléments identiques, il est nécessaire de prendre certaines précautions. Une solution consiste à marquer les éléments déjà choisis, par exemple à l’aide d’un troisième tableau d’indicateurs (le tri est alors stable), ceci n’est qu’un exemple, d’autres possibilités existent, peut-être avez-vous une idée ?
Tri par comptage
Suivant les données à trier, il peut être plus efficace de construire un algorithme de tri spécifique. Par exemple, si le tableau contient un grand nombre de valeurs similaires (exemple : gestion annuelle d’un stock où la plupart des articles entrent et sortent plusieurs fois par jour), on peut utiliser l’algorithme simple (par création) consistant à rechercher l’élément le plus petit, compter le nombre de ces éléments, les mettre dans le tableau destination, et répéter l’opération jusqu’à la fin du fichier destination. Si vous êtes forts, vous pouvez également prévoir le cas où le nombre de valeurs différentes est suffisamment faible pour pouvoir utiliser un tableau de compteurs, ce qui permet d’effectuer le comptage en un seul balayage du fichier.
Tri basique
Dans la cas où les valeurs sont bornées (c’est à dire comprises entre un minimum et un maximum connus à l’avance) et en nombre fini, on peut utiliser ce tri. Par exemple si toutes les clefs sont des entiers entre 000 et 999, on peut séparer le tableau en 10 parties en fonction des centaines, puis récursivement traiter les dizaines puis les unités (tri en base 10). Evidemment, un tri en base 2 sera plus efficace sur ordinateur : du début du tableau,on avance jusqu’à trouver un nombre commençant par 1, puis depuis la fin jusqu’à trouver un nombre commençant par 0. On les échange et l’on continue jusqu’à croisement des deux côtés. Puis on recommence (récursivement par exemple) sur le bit suivant, jusqu’à tri complet. Pour trier des valeurs alphabétiques, on peut effectuer un tri en base 26, sur les N premiers caractères (N pouvant valoir 2 ou 3 par exemple), le fichier est alors presque trié. Il est alors plus efficace d’effectuer un tri par insertion (passe de finition) plutôt que de répéter le tri basique jusqu’à tri complet.
sinon en php il y a array_sort…
Voilà, donc a la maison, vous pouvez soit tous les faire pour en faire qu’un au final, soit ne rien faire parceque vous n’avez pas la tête à ça comme moi en ce moment et vous le ferez en tp….
Micous, si tu veux, tu peux les faire en VBA, ça pourrait être drôle.
Note : la fonte est passée de 80% à 75%, c’est plus petit mais je trouve que ça rend mieux. que disent vos yeux ?
hé oui, toi, utilisateur/trice du mac (book pro) tu sais que tu peux faire quelques effets avec la webcam….
allez qui peut être plus beau/belle que lui (connu sous le pseudo de tronche de cake) ?
(au moins 3 commentaires et je poste la photo en question)
3 commentaires, donc la photo.
il est beau hein :p
bah, je vais pas me plaindre, j’ai des journées fort chargées, des soirées géniales, et tout et tout.
Ma mère me demandais si je me plaisait a Strasbourg. Je ne peux pas lui dire non. C’est pas pareil (mais alors pas du tout) qu’à Metz. L’autonomie a fait son apparition et fait agir d’une nouvelle façon. Les gens de Metz me manquent mais on se rattrape les week ends, donc tout va.
Les soirées des deux dernières semaines ont étés mouvementées de déplacements, de repas tardifs, de nuits courtes … une vie d’étudiant quoi. Je rentre à Metz ce soir parce que plus cours pour la fin de la semaine et je vais sur Lyon ce weekend, histoire d’en profiter un max vu que certain(e)s vont passer Noël loin.
J’ai mangé avec deux actrices la semaine dernière (sisi je vous jure), pas encore connues sur la scène mais que pour les VIP (oui ca va mes chevilles).
Je squatte toujours autant de blogs, donc je récupère quelques images par ci par là, notemment celle ci dessus, qui pourrait être moi. Je pense depuis quelques temps et ça se voit (à ce qui parait) et ça m’angoisse (certains stressent pour des exams) et ça va jamais comme je veux donc ça me saoule.
Bref, moi je vous dis à je sais pas quand, vu que le l’auteur du blog se traine un poil. Je dirais juste que certaines choses se sont accélérées et qu’elles changent et que je sais pas ce que ça va devenir.
et vous regardez encore mon blog …. je ne sais plus quoi vous dire. Ah si, restez.
bon petit week end sur metz et j’ai pas envie de taffer (j ai un exam demain et un après demain), bref. Le K850i (j’hésitait avec le N81 de chez Nokia) commence a pointer le bout de son nez sur le marché (enfin), bientôt en boutique (Orange et SFR) donc je vais pouvoir commencer a comparer et a savoir où je le prends …
Ce qui est sur c’est qu’il serat bleu et que je prendrais plus de téléphone avec un joystick !! Bref, donc avant noël, si il me reste des sous* ….
note : en droit/eco c’est des pourri, ils (elles) ont eu des vacances, déjà qu’ils font pas grand chose en semaine ….
note * : donc pour avoir des sous, faut plus que je fasses de sorties, plus que je fasses des cadeaux, et que j’ai pas de copine (si on a une copine on lui fait des cadeaux …) donc, je suis mal barré.
Concerant pizdaus, c’est un peu comme bashfr ou chuck norris, j’y squatte trop souvent, alors ça déteint….
Pour micous : Chuck Norris peut gagner une partie de puissance 4 en trois coups.
