Discussion :

[Onimaru]

Salut à tous, j'ai une petite question :

Code Delphi :

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

1
2
3
4
5
6
7
8
9
10
11
12
procedure Trier(var T : array of integer);
var I, J, Temp : integer;
begin
 for I := High(T) downto 1 do
  for J := 0 to I do
   if T[J] > T[I] then
    begin
     Temp := T[J];
     T[J] := T[I];
     T[I] := Temp
    end
end;

De quel algorithme de tri s'agit t il ???

[prgasp77]

Si I allait de 1 à High(T) alors ce serait un tri par insertion.
Cdlt,

[pseudocode]

De quel algorithme de tri s'agit t il ???

[ame="http://www.youtube.com/watch?v=gWkvvsJHbwY"]la réponse en image[/ame]

[prgasp77]

Au temps pour moi, c'est bien celui-ci.

[ame="http://www.youtube.com/watch?v=k4RRi_ntQc8"]« I think the bubble sort would be the wrong way to go. »[/ame]

[Onimaru]

C'est quoi ce tri alors ???
Il a les caractéristiques du tri par sélection et insertion et bulles.
La première fois que j'ai essayé de trier un tableau j'ai pensé à ça mais je ne sais pas encore de quel tri il s agit ???

[Invité]

Bonjour,

Comme l'a dit pseudocode, il s'agit du tri à bulles.

[Onimaru]

mais le tri à bulle procède en prenant chaque deux éléments successifs d'après ce que je sais ???

[Invité]

Ce tri :
- regarde les éléments 1 et 2, il les permute s'ils sont pas dans le bon ordre.
- regarde les éléments 2 et 3, il les permute s'ils sont pas dans le bon ordre.
- regarde les éléments 3 et 4, il les permute s'ils sont pas dans le bon ordre.
- regarde les éléments 4 et 5, il les permute s'ils sont pas dans le bon ordre.
- ...
- regarde les éléments n-1 et n, il les permute s'ils sont pas dans le bon ordre.

A là fin de cette passe, il n'y a qu'un élément de trié : c'est le maximum. Ce maximum est maintenant placé tout à droite du tableau. On ne s'en occupe plus. On recommence donc la même procédure sur le tableau mais sans considérer son dernier élément.

On fait ça jusqu'à ce qu'on ne considère plus qu'un seul élément (le tableau est alors trié).

Dans ton code, la variable qui joue le rôle de la taille du tableau que l'on considère à l'étape courante, c'est la variable I. Au début elle est égale à la taille tu tableau complet, et à chaque étape, on met l'élément maximum (qui n'a pas encore été trié) à droite, et on diminue la taille du tableau de 1.

C'est exactement comme le tri par sélection sauf qu'au lieu d'échanger directement le maximum avec l'élément non trié le plus à droite, on échange successivement le maximum avec tous les éléments qui le séparent de sa position finale ... ce tri n'est pas très utile.


------------------
EDIT : je me suis trompé aussi, ce n'est effectivement pas le tri à bulles

[prgasp77]

Relisez attentivement le code posté : les deux éléments comparés ne sont (a priori) pas successifs. Mais d'un autre coté, ce n'est pas non plus un tri par insertion (j'ai moi aussi été trop vite).

Onimaru : ton algo n'est pas un algo classique de tri, mais il offre la même inefficacité que le tri à bulles (sans offense).

[pseudocode]

Relisez attentivement le code posté : les deux éléments comparés ne sont (a priori) pas successifs. Mais d'un autre coté, ce n'est pas non plus un tri par insertion (j'ai moi aussi été trop vite).

Ah oui, effectivement, on ne compare pas les éléments successifs. Moi aussi j'ai lu le code trop vite.

C'est donc un tri par sélection, mais avec permutation des candidats intermédiaires (ce qui ne sert pas a grand chose).

[Onimaru]

Salut à tous,
merci pour les réponses : donc ce tri est un tri hybride entre le tri par sélection est le tri par bulles, effectivement son principe est comme expliqué par hellfoust et c'est comme ça que j'ai pensé la première fois que l'ai écrit.

ton algo n'est pas un algo classique de tri

c'est ce point précis qui m'a poussé a poser cette question sur le forum et non pour prouver qu'il est ultra efficace !!!
en effet dans les examens chaque fois qu'il y a question de trier des éléments(le but de la question n'est pas le tri) j'utilise cette méthode car elle est simple tout court mais personne ne le comprend directement.
En tout cas personnellement je l'ai classé comme tri par sélection, mais le fait d'avoir plusieurs permutations intermédiaires m'a rendu perplexe si vous voyez ce que je veux dire.

[Invité]

en effet dans les examens chaque fois qu'il y a question de trier des éléments(le but de la question n'est pas le tri) j'utilise cette méthode car elle est simple tout court mais personne ne le comprend directement.

Tu peux faire le tri par sélection en rajoutant une seule ligne (12 lignes pour ta version, 13 lignes pour celle-ci) :

Code Delphi :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
procedure Trier(var T : array of integer);
var I, J, Max, IndiceDuMax : integer;
begin
 for I := High(T) downto 1 do
  for J := 0 to I do
   if T[J] > Max then
    begin
     Max := T[J];
     IndiceDuMax := J;
    end
   T[IndiceDuMax] = T[I];
   T[I] = Max;
end;

[Onimaru]

Tu peux faire le tri par sélection en rajoutant une seule ligne (12 lignes pour ta version, 13 lignes pour celle-ci) :

Code Delphi :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
procedure Trier(var T : array of integer);
var I, J, Max, IndiceDuMax : integer;
begin
 for I := High(T) downto 1 do
  for J := 0 to I do
   if T[J] > Max then
    begin
     Max := T[J];
     IndiceDuMax := J;
    end
   T[IndiceDuMax] = T[I];
   T[I] = Max;
end;

Oui je sais ça, la différence réside dans le fait que le tri par sélection ne permute que le minimum(ou le maximum) alors que l'algorithme en question fait des permutations supplémentaires.