Tri d'un tableau par ordre croissant

**goaks** · 07/06/2007, 18h55

Salut, j'aimerai savoir comment faire pour trier un tableau de valeurs dans l'ordre croissant car je ne vois pas comment un algorithme peut faire cela ? Merci.

**droggo** · 07/06/2007, 19h05

Hia,

Un algorithme peut faire ça quand c'est un algorithme de tri.

Google et/ou Wikipedia te donneront des tas de réponses en une petite fraction de seconde.

**LadyWasky** · 07/06/2007, 23h13

il y a plusieurs algorithmes de tris existant.

Mon préféré, c'est celui qu'on appelle le tri de shell (enfin, on m'a toujours dis qu'il s'appelais comme ça).

Même si ce n'est pas le plus performant, il à le mérite d'ètre déjà très performant en restant très simple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
//c'est du simili pascal
N : nombre d'éléments d'un tableau
var i,j:entiers;
     Tableau : Tableau d'entiers indicés de 0 à N-1;
     Temp:entier; //variable temporaire
begin
  for i:=0 to N-2 do                 //on fait varier i de 0 à N-2
    for j:=N-1 downto (i+1) do   //on fait varier j de N-1 à (i+1)
      if Tableau[j]<Tableau[i] then  
      begin
        temp:=Tableau[i];
        Tableau[i]:=Tableau[j];
        Tableau[j]:=temp;
      end;
end;

C'est pratiquement le même code que le tri à bulle. A ala différence du tri à bulle, dans celui-ci, la variable j par de la fin du tableau, pas encore triée pour remonter vers ce qui est déjà trier (dans le tri à bulle, avec j, on descend le tableau pour faire remonter les "bulles").

l'algo que je viens de te donner va trier par ordre croissant, pour trier par ordre décroissant il s'agit juste de changer le signe de l'égalité.
Après, pour comprendre comment ça marche, tu te fais un tableau à la main, avec 10 cases que tu remplies de chiffre au hasard, et tu suis le code à la main... et voilà...

**Gwylom** · 08/06/2007, 01h45

waskol, j'ai l'impression que ton tri ressemble plus à un tri sélection (ou tri par extraction, c'est le même) qu'à un tri shell.

Mais le fait de partir les éléments de j depuis la fin vers i est plutôt élégant, puisque ça permet de trier quelques éléments de la fin du tableau, alors qu'en parcourant dans l'autre sens, comme c'est le cas dans la version que je connais de ce tri, on les tri dans le mauvais ordre. Alors que le pire des cas pour cet algo est que le tableau soit exactement trié dans le mauvais ordre...

De mon coté j'aime bien le tri fusion, il est joli

Pas la peine de donner des détails ici, google est super fort en détails...

**FabaCoeur** · 10/06/2007, 13h39

Voila ce que je pourrais apporter en matière d'algorithme de tri:

1) J'utilise tout le temps le tri par selection, car il a le mérite d'être simple à programmer et à retenir. Il a une complexité de a peu près O(n²). Le voila:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
donnée *tab[n];
entier i,j,min;
donnée temp;
 
 
// Parcours du tableau
pour i allant de 0 à n, i+1
faire
 
	min <- i
 
	// Parcours d'un sous tableau
	pour j allant de i+1 à n, i+1
	faire
 
		si tab[j] < tab[min]
		faire
			// On garde l'indice du minimum du sous tableau
			min <- j
		fsi
 
	fpour
 
	// On inverse le minimum avec le 1er element du sous tableau
	temp <- tab[min]
	tab[min] <- tab[j]
	tab[j] <- temp
 
fpour

2) Le "quicksort" est un des tris les plus performant. En revanche, il est loin d'être le plus simple (ni à retenir, ni à programmer) car il utilise plusieurs fonctions avec des appels récursifs.

3) Le tri bulle est à bannir d'après moi, il est vraiment l'un des moins performant, de plus je le trouve encore moins simple que le tri par selection...!

4) Il existe bien d'autre tris (par insertion, ect)...

**ol9245** · 12/06/2007, 09h14

Vos considérations sur la difficulté à programmer un quicksort me laissent perplexe. Qui préfère se palucher un algo de tri (polynomial) à la main au lieu de copier/coller un algo réputé (et quasi linéaire) et qui marche sans passage par la case debug ?

J'ai lu Sedgewick avec délices. 10 ans après son bouquin est encore sur mon bureau ! Pourtant, je trouverais baroque de bidouiller moi même un seul de ses algos.

Il n'y a qu'à la fête des mères que les femmes portent des coliers en nouilles fabriqués par leurs gamins. Sedgewick (et les autres) fabriquent des bijoux ? je les porte ! Chacun son métier.

Et si un de mes gars joue à réinventer la roue (de secours, la polynomiale, justement), je lui demande gentilement de s'amuser à ça le soir si ça lui plait. Aux heures de bureau, il est prié d'utiliser Google.

**FabaCoeur** · 12/06/2007, 20h39

Pour ma part je parlais d'un point de vue purement étudiant.
Si on regarde le message à l'origine de la discussion:

Envoyé par goaks

Salut, j'aimerai savoir comment faire pour trier un tableau de valeurs dans l'ordre croissant car je ne vois pas comment un algorithme peut faire cela ? Merci.

La solution évidente c'est Google...! Comme dans beaucoup de topic à ce compte là.
Après aller copier/coller un algo de quicksort, oui ca marche, mais d'un point de vue "apprentissage" je trouve pas que ça soit au top

**souviron34** · 12/06/2007, 20h52

Envoyé par ol9245

J'ai lu Sedgewick avec délices. 10 ans après son bouquin est encore sur mon bureau ! Pourtant, je trouverais baroque de bidouiller moi même un seul de ses algos.
..

En plus, t'es radin avec Sedgewick

Le premier volume, "Algorithms in Fortran" date de 1990, suivi de "in C" (d'ailleurs, c'est tous des "traductions" les uns des autres par des étudiants.. une fois une bonne formule

autant l'exploiter) (ça se voyait sur le "In C", dans un certain nombre d'algos les boucles partaient de 1.. ).

Mais c'est vrai que c'est le meilleur (et beaucoup plus clair que NR)...

**ol9245** · 13/06/2007, 00h20

Envoyé par FabaCoeur

Après aller copier/coller un algo de quicksort, oui ca marche, mais d'un point de vue "apprentissage" je trouve pas que ça soit au top

Les temps ont changé. Je préfère aujour'hui un gars qui connait le principe général de 200 algos de base et sait comment en trouver les sources sur Internet qu'un geotrouvetout qui aura toujours sa petite idée maline de comment le faire tout seul. L'enseignement de l'informatique devrait évoluer vers plus de culture générale au détriment éventuellement d'une certaine dextérité, qui était davantage recherchée par le passé quand Internet n'existait pas et que chaque programmeur se battait seul, parfois pendant des jours, sur un bug ou une insulte du compilo. Une preuve ? le nombre de post, ici, sur DVP, ou, sans connaire la solution, il est possible d'y répondre avec en 2 minutes avec Google.

**ol9245** · 13/06/2007, 00h32

Envoyé par souviron34

... Mais c'est vrai que c'est le meilleur (et beaucoup plus clair que NR)...

Pour un autodidacte sans énorme bagage en math, NR est souvent le seul livre tout simplement lisible. (mais les algo dedans : pas la peine ! transcription littérale du Fortran, la pseudo version """C++""" qui ignore les template, et pas une seule ligne de commentaires. Tout juste bon pour du copier-coller !)

**HanLee** · 13/06/2007, 01h52

Le truc qui me fait réagir dans ce que FabaCoeur a dit, c'est que le quicksort était difficile à implémenter, alors que non, c'est justement un algorithme récursif, ce qui se traduit souvent par une facilité de mise en oeuvre (et c'est le cas !).

Le truc point délicat c'est la séparation des éléments du tableau à l'aide du pivot choisi...

------

Sinon, normalement tout développeur a un bagage algorithmique de base qui normalement devrait lui permettre de s'en sortir, sans bidouiller : listes, piles, files, arbres, graphes et complexité sont des choses connues, ainsi que le principe diviser pour régner.
Les tris sont normalement connus.

Avec ça, on doit savoir faire plein de choses de manière autonome, non ?
Ce n'est plus vraiment l'époque des géotrouvetout.

**ol9245** · 13/06/2007, 02h40

Envoyé par HanLee

Sinon, normalement tout développeur a un bagage algorithmique de base qui normalement devrait lui permettre de s'en sortir, sans bidouiller : listes, piles, files, arbres, graphes et complexité sont des choses connues, ainsi que le principe diviser pour régner.
Les tris sont normalement connus.

Avec ça, on doit savoir faire plein de choses de manière autonome, non ?
Ce n'est plus vraiment l'époque des géotrouvetout.

En traitement d'image, en traitement du signal, en cryptographie, en IA, en analyse numérique, pour ne prendre que les premiers exemples, le nombre d'algorithmes importants, couramment mis en oeuvre, a explosé en même temps que l'emprise de l'informatique dans la vie de tous les jours. La performance d'un programmeur (temps de travail sur un projet, limpidité du code produit) et sa créativité (originalité et efficacité des solutions) sont directement proportionnelles au nombre de ces algos qu'il sait * nommer, * décrire sommairement et *, trouver une implémentation sur Internet

**Senyk** · 13/06/2007, 15h29

Pas tout à fait d'accord, le passage par l'implémentation est encore indispensable pour apprendre. Elle sert aussi à s'approprier un algorithme. Comment avoir du recul sur tel ou tel algo si on ne met pas un minimum les mains dans le cambouis ?

Prends par exemple les problèmes d'optimisation. Pour un problème, pourquoi prendre un algo de colonie de fourmie plutot qu'un recuit simulé ou alors une simple résolution par programme linéaire ?
Seul l'expérience d'un développeur pourra choisir selon le contexte ... Je suis pas persuadé que google peut se substituer à ce niveau à la réimplementation de ces méthodes dans le but d'acquérir cette expérience.

Le meilleur moyen pour comprendre les tris reste encore de les implémenter et de les tester....

**ol9245** · 13/06/2007, 16h34

Envoyé par Senyk

Le meilleur moyen pour comprendre les tris reste encore de les implémenter et de les tester....

je suis d'accord avec toi sur le principe car ce que tu dis va de bon sens. mais ca ne résiste pas à 'observation objective de la réalité de l'informatique d'aujourd'hui.

Contre exemple n°1, le mien : j'aime les algos et j'en ai même publiés dans des revues scientifiques, mais je ne me suis j a m a i s fait c### à programmer un tri. En revanche, je lis, je fouine (sur DVP par exemple

) et j'essaye de garder les pistes en tête. Pour finir, je vais finir par savoir programmer un tri lol, mais ma démarche aura été inverse de celle de l'ancien temps : la culture générale sur les algos d'abord. La dextérité ensuite.

Raisnonnement n°2 : le nombre d'algo qu'un informaticien doit connaitre croit exponentiellement. Le nombre d'heures de cours pour devenir informaticien ne peut au mieux que croitre linéairement. Quel choix faut-il faire ? Mon idée est claire et personne ne me fera changer d'avis : mettre la priorité sur la culture algorithmique, celle qui permettra de trouver les solutions sur Internet. Et si on fait ce choix là, c'est donc au détriment de quelque chose d'autre et cette autre chose, je veux bien sacrifier la dextérité.

Exemple n°3 : pour illustrer pourquoi la dextérité est moins importante que la culture algorithmique, encore une histoire qui m'est arrivée. Il y a un petit bout de temps, j'ai passé 2 semaines à chercher du côté des arbres équilibrés la solution à un problème. Et puis un jour, en cherchant des conseils dans un forum, un mec m'a répondu le plus petit post que j'ai jamais vu. Il n'y avait qu'une demi-ligne : "looks like a priority queue can do the job". Priority queue ? je ne savais même pas ce que c'était (c'est pourtant de toute beauté !). Et c'est ce qu'il me fallait ! Moralité : la dextérité ne sert à rien sans la culture. Et la culture, ce sont des centaines d'algos différents dont il faut connaitre au moins de loin l'existence et le principe général. C'est le rôle de l'école d'apprendre ça. La dextérité viendra naturellement par la pratique.

**souviron34** · 13/06/2007, 16h52

entièrement d'accord

Et d'ailleurs , au delà de ça, je dirais que le fond de tout est le bon sens. Mieux vaut une tête bien faite qu'une tête bien pleine....

Personne ne saura jamais tout sur son domaine. Ce qu'il faut, cest savoir OU chercher. Et savoir adapter...

C'est d'ailleurs à mon avis un échec patent de l'enseignement scolaire de l'info (entre autres). On limite la pensée aux derniers langages en vogue, ou au contraire à la théorie (de l'algo, etc..).

Alors que le fond, c'est que les langages ne sont que des outils, et que en général, les grandes idées d'algo (voir d'ailleurs la 3ième remarque de ol9245) sont des idées simples, la plupart sans maths complexes..

D'ailleurs, les solutions les plus élégantes sont en général basées sur le même principe.. Des maths simples, du bon sens, beaucoup de réflexion, quelques recherches pour voir les idées des autres, et pouffff....

Alors que si on regarde (et/ou apprend) avec l'implémentation, d'abord il faut que le code soit bon , clair, bien expliqué (très rare), et souvent de plus il est optimisé, et éventuellement adapté à un métier/forme de pensée donné/e.

Et donc souvent au contraire on se forme par ce biais à "pourquoi faire simple alors qu'on peut faire compliqué" .... qui est déjà assez répandu comme état d'esprit sans avoir à en rajouter (il suffit de voir certains posts sur dvp..)...

**Senyk** · 13/06/2007, 17h54

Envoyé par ol9245

Moralité : la dextérité ne sert à rien sans la culture.

L'implémentation pour moi, ce n'était pas pour augmenter la dextérité.... Je suis tout à fait d'accord sur le fait que la maîtrise technique nécessite la culture.

Mais je parle d'implémenter pour maîtriser le principe d'un algo. Pour comprendre le pourquoi ? Pour comprendre quelles sont ses qualités et ses défauts etc ....

Les projets en universités comme la création d'un compilateur, l'écriture d'un allocateur mémoire, etc ... sont plus là pour illustrer un cours de compilation ou de systèmes d'exploitation que de maîtriser un langage ou une technologie.

Bref, ré-implementer un algorithme célébre est un moyen pour apprendre la culture informatique...

**ol9245** · 13/06/2007, 18h27

Envoyé par Senyk

Bref, ré-implementer un algorithme célébre est un moyen pour apprendre la culture informatique...

l'horloge marque t=0.
On nous dis à tous les deux : le quick sort consiste à séparer le tableau en 3 tas : les grands, les petits, et ceux qui sont égaux au pivot choisit pour départager grands et petits. On concatène ensuite les tas dans le bon ordre. La même recette est appliquée récursivement pour trier les grands, puis les petits. J'ai les grandes lignes. je mémorise le shéma, et je passe à la suite.
L'horloge marque maintenant t=30 secondes.
maintenant, deux choix.
le tien : tu te farcis l'implémentation.
t=2 h. Tu as gagné en dextérité. mais pas en culture car tu ne connais toujours que le quick sort
le mien : je continue la lecture de ce bouquin passionnant. A t=2h je suis à la page 100. J'ai moins de dextérité, mais plus de culture.

**Senyk** · 13/06/2007, 18h57

Envoyé par ol9245

J'ai les grandes lignes. je mémorise le shéma, et je passe à la suite.

Tu mémorises pour combien de temps?

t = 2H, tu es à la page 100 mais tu as totalement oublié la page 10!

Continuons à t = 1 journée ... je sais faire au moins un tri, je suis plus près de l'oublier et toi ?

Qui te dit que les priority queues, tu en avais pas entendu parler dans un livre et que depuis tu l'as oublié.

Sans rire, la grande majorité des personnes (moi le premier) ont besoin d'un minimum d'entrainements et de manipulations avant d'assimiler une notion.

Algorithmique n'étant pas si évident que ça comme matière.... l'implementation reste donc un bon moyen de s'entraîner et d'acquérir de la culture

Bon le topic dévie un peu de son origine ... ca mériterait que cette discussion continue ailleurs.

**Gwylom** · 14/06/2007, 01h54

Envoyé par ol9245

le quick sort est un tri par fusion récursif : tu applique la même recette pour trier chacun de tes demi-tableaux. J'ai les grandes lignes. je mémorise le shéma, et je passe à la suite.

Le tri fusion est déjà récursif... Le quick sort c'est autre chose, il te faudra un peu plus de t...