Discussion :

[argon]

Bonsoir tout le monde

Voici l'algo actuel du tri, en java.

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
30
31
32
33
34
35
 
public void tri()
{
 
longueur=tab.length;
 
 
	do{
 
	temp=0;
 
	p=0;
 
	i=0;
 
	while(!(i==longueur-1)){
 
 
	if(tab[i] >tab[i+1])
				{
 
	temp=tab[i];
	tab[i]=tab[i+1];
	tab[i+1]=temp;
		p=1;
		}
 
		i = i +1;
 
		}
 
 
}while(p==1);
 
}

Voici ma question, il faut une itération de i de l'algo, je dois tester les permutation que sur les valeurs entre t[0] et t[i].

Moi même, j'ai du mal à comprendre la question.

Elle est sur ma feuille d'exercice.

Pouvez vous m'aider.

Merci

Cordialement

A bientôt

[Jedai]

Donnes nous la question exacte, car ton explication est incompréhensible. S'il s'agit déjà de la question exacte, demande à ton prof d'écrire en Français...

--
Jedaï

[Gnux]

Salut
J'ai rien compris de ce que tu veux faire...Tu pourrais préciser

[argon]

Re

Voici la question exacte:

il faut une itération de i de l'algo, on ne teste les permutations que sur les valeurs entre t[0] et t[i].

a+

[Freyja]

pffiou je n'arrive pas a comprendre non plus...

Ca veut dire quoi "faire une itération d'un nombre" ???

[benratti]

En francais, une question se termine par un point d'interrogation. Ici, je ne vois qu'une affirmation... On ne peut pas t'aider tant que la question n'est pas clair.

[lyxthe]

Je confirme cette phrase n'est déjà pas une phrase compréhensible, et est encore moins une question compréhensible. T'es sur qu'elle continue pas sur une autre ligne ou qu'il n'y avait pas d'autres mots sur la ligne d'avant ? Parce que en l'occurence tu n'as pas un problème d'informatique mais bel et bien de grammaire. Dis à ton prof de retourner au cp ou bien penses à prendre des cours de lectures. C'est selon. Ceci étant dit une fois le problème résolu, je serais curieux de connaitre la vrai question, tiens nous au courent

PS : ton tri n'a rien d'efficace. Il est en O(n^2). Si tu cherches, les meilleurs tris sont en O(n*log(n))

[Freyja]

PS : ton tri n'a rien d'efficace. Il est en O(n^2). Si tu cherches, les meilleurs tris sont en O(n*log(n))

Bah normal il travail sur le tri a bulle !
Je ne pense pas qu'il recherche des algo de tri. Ce n'est qu'un exercice, peut etre pour leur montrer que le tri à bulle c'est beuurrk


Sinon tu ne peux pas nous envoyer tout l'exo en entier ? Il y avait peut etre autre chose avant ? ca peut nous aider à essayer de décoder ton prof

[DaZumba]

Ce n'est qu'un exercice, peut etre pour leur montrer que le tri à bulle c'est beuurrk

Il suffit de le dire, ce n'est pas la peine de demander aux etudiants d'implementer un tri a bulle. Ils risquent de l'utiliser quand meme... Comme l'ecrivent bien les auteurs de Numerical Recipes:

We will draw the line, however, at the inefficient N2 algorithm, beloved of elementary computer science texts, called bubble sort. If you know what bubble sort is, wipe it from your mind; if you don’t know, make a point of never finding out!

[Freyja]

Il suffit de le dire, ce n'est pas la peine de demander aux etudiants d'implementer un tri a bulle. Ils risquent de l'utiliser quand meme... Comme l'ecrivent bien les auteurs de Numerical Recipes:

Je ne pense pas qu'il implemente, c'est juste un exemple, mais bon le probleme n'est pas la :p

[j.p.mignot]

Une fois de + Numerical Recipes apporte une analyse pertinente!
En ce qui concerne la demande, j'ai aussi un peu de mal à trouver le fil directeur
En ce qui concerne les méthodes de tri, cela a déjà été débattu plusieurs fois sur ce forum.
On trouve pas mal d’articles. Voir par exemple
http://fr.wikipedia.org/wiki/Tri

[PRomu@ld]

Il suffit de le dire, ce n'est pas la peine de demander aux etudiants d'implementer un tri a bulle. Ils risquent de l'utiliser quand meme...

Si la taille des données en entrée est assez petite et qu'on a besoin de trier qu'une seule fois, un tri en O(n^2) est utilisable. Il faut trouver le compromis entre le temps que le passe à écrire et le temps que l'on gagne.

Les tris a forte complexité ne sont pas tous là pour des raisons historiques, avec des tris adaptifs (en fct de la taille d'entrée), on peut les utiliser car ils sont plus rapide que ceux en O(n log n), surtout avec la puissance des machines actuelles, de plus n'oubliez pas que la notation O cache des constantes ...

[lyxthe]

D'où l'interet de séparer l'étude algorithmique pure sans relation avec la puissance des machines, et faites uniquement sur papier (théorie des graphes, prgrammation linéaire etc...) et la programation réelle selon différents langages (c++ java...).
Je suis étudiant en IUP GMI à Montpellier, et j'ai découvert l'algorithmie en cours, et je dois avouer que c'est nettement plus intéressent selon moi que la programmation pure et dure. Et en cours il y a une réelle distinction entre "la théorie et la recherche en Algorithmie" , et "la pratique et la programmation sur machines".
Enfin il faut bien faire le lien entre les deux pour expliquer aux programmeurs à quoi sert un algorithme de basse complexité, mais il n'en peche qu'à trop mélanger les deux on finit par s'empatouiller les pédales.
Enfin c'est mon avis d'étudiant. :p

[argon]

Bonsoir tout le monde

Quand je dis:

il faut une itération de i de l'algo, on ne teste les permutations que sur les valeurs entre t[0] et t[i].

je parle de la boucle, i<n, de là suive les permutation.

Cordialement

A bientôt

[lyxthe]

Suis-je le seul à n'avoir toujours pas compris la question?

[Freyja]

+1
Et ca devient moins clair !!

je parle de la boucle, i<n, de là suive les permutation.

Ca veut dire quoi la ???
pffiou je ne dois pas parler la même langue que vous lol.
Heureusement que je ne fais pas les même etudes que vous :p

[borisd]

il faut une itération de i de l'algo, on ne teste les permutations que sur les valeurs entre t[0] et t[i].

Je n'ai pas regardé ton implémentation du tri à bulles, mais ça ne serait pas plutôt entre t[0] et t[longueur-i] (ou même t[longueur-k], k>=i), le reste du tableau étant forcément trié ?
Dans ce cas, il suffit de garder à chaque itération l'indice ("permut") du dernier élément permuté, et de s'arrêter de comparer à cet indice au lieu d'aller jusqu'à la fin du tableau pour l'itération suivante.
On s'arrête alors quand "permut=0".