Discussion :

[sidahmed]

Bonjour,comment trier un tableau avec une seule boucle,merci

[j.p.mignot]

Ce code fait une seule boucle mais cela est aboslument CONTRE PERFORMANT par rapport à des méthodes de type quick sort !!!

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
 
procedure triller( start_point, end_point : integer; var T );
var i : integer;
   begin
   i:=start_point-1;
       repeat
       inc(i);
       if i < Start_point then i:=Start_Point;
       if T[i] > T[i+1] then
          begin
          echanger T[i] et T[i+1]
          dec(i,2);
          end;
       until i=end_point-1
   end;

[Rafy]

Hum aller voir la FAQ...

[pcaboche]

Tu peut même faire mieux: un tri sans aucune boucle, entièrement récursif! (ben oui: comment vous croyez qu'on fait avec des langages fonctionnels?)

Le tri quicksort, c'est bien. Le tri fusion (merge sort), c'est mieux! Le tri radix, c'est encore mieux! (mais pas applicable à tous les types de données)

Sinon, j.p.mignot le tri dont tu parles, ça ne serait pas le "gnome-sort" par hasard?

[j.p.mignot]

Je ne sais pas si cela porte un nom!
J'ai écrit et utilisé une fois la méthode présentée pour éviter tout risque de montée incontrôlée dans la stack ce qui est un risque potentiel avec toutes méthodes récurcives.
Mais il existe bien des techniques
http://fr.wikipedia.org/wiki/Tri

[Jean-Marc.Bourguet]

Je ne sais pas si cela porte un nom!
J'ai écrit et utilisé une fois la méthode présentée pour éviter tout risque de montée incontrôlée dans la stack ce qui est un risque potentiel avec toutes méthodes récurcives.
Mais il existe bien des techniques
http://fr.wikipedia.org/wiki/Tri

http://www.cs.vu.nl/~dick/gnomesort.html

[pcaboche]

pour éviter tout risque de montée incontrôlée dans la stack ce qui est un risque potentiel avec toutes méthodes récurcives.

C'est vrai qu'il y a plein de critères à prendre en compte dans un algorithme de tri:

- la vitesse
- la quantité de mémoire utilisée (sur place ou pas)
- la stabilité du tri (facteur souvent négligé)

- d'autres, suivant le projet :
ex: la manière dont le tri accède aux éléments (si il faut, par exemple, charger les éléments lorsqu'ils ne sont pas présents en mémoire, il vaut mieux que le tri porte sur des éléments consécutifs. Ce n'est pas le cas du tri par tas)

Le tri fusion est très approprié (rapide, stable, pas d'aller-retour dans la liste) si ce n'est qu'il utilise plus de mémoire.


Pour ce qui est de la récursivité, dans les langages fonctionnels, on ne peut pas faire autrement. Si je parlais de récursivité, c'est que sidahmed sous-entendait que le minimum de boucle pour trier un tableau était 1; or c'est faux: avec la récursivité on a 0 boucle. C'était une sorte de boutade !

[pcaboche]

Le "gnome sort" a des propriétés interessantes:
- il est "sur place" et utilise très peu de mémoire
- il est stable (enfin il me semble)
- son code est de très petite taille. Une fois compilé, ça devrait être pareil

Il peut donc être très intéressant dans les cas où on peu de mémoire à disposition (le genre système embarqué)

Par contre, il a un inconvénient:
- il est très lent

[Jedai]

Un quicksort optimisé ne prend pas tant de place que ça une fois compilé (d'autant qu'il faut pas abuser : même sur de l'embarqué, 30 octets de différence c'est pas si gros...), il est beaucoup plus rapide que le gnome-sort et est aussi sur place. (par contre c'est vrai qu'il prend une place en O(log(n)) lors de l'exécution alors que le gnomesort est en O(1)...et il n'est pas stable en général)

--
Jedaï

[pcaboche]

Je confirme, quicksort n'est pas stable (ça peut être gênant dans certains cas). Si on veut être pointilleux, on peut dire aussi que les performances de quicksort dépendent du choix du pivot, mais il faut vraiment prendre des cas défavorables complètement fabriqués pour l'occasion.

Dans la plupart des langages, c'est l'algorithme merge sort qui est utilisé pour les fonctions de tri, d'abord pour des raisons de stabilité et ensuite parce qu'il est performant (dans la majorité des cas, le problème de la mémoire est secondaire: pour trier des petits tableaux, ça passe)

Après, il peut être intéressant de se demander quel algorithme est utilisé pour trier des gros fichiers (accès séquentiel aux éléments, pas la possibilité de mettre tout le contenu du fichier en mémoire, utilisation de cache...) mais à mon avis, c'est un dérivé de merge sort, basé sur de manipulations de fichiers temporaires, qui est utilisé.

[j.p.mignot]

Je viens d'apprendre que j'ai "réinventé" un algorithme ( de 3 lignes!) existant!
Blague à part les seuls avantages que je lui ai vu étaient
- code très petit ( important dans certains processeurs embarqués)
- garantie de ne pas aller dans la stack trop loin (encore plus important pour des petits systèmes embarqués disposant de très peu de mémoire )

J'avais cité cet exemple uniquement car l'initiateur de cette discussion souhaitait un algorithme en une boucle.

Personnellement dans la plus part des cas, sur PC, j'utilise QuickSort

[ToTo13]

Bonjour,

si tu connais le plus grand élément et le plus petit, tu peus trier ton tableau sans faire de comparaisons. c'est le tri le plus rapide.

[j.p.mignot]

???
si j'ai 4 chiffres, par exemple a=2 b=1 c=4 d=3, que je connaisse min et max et que je veuille ordonner (a,b,c,d) dans l'ordre croissant par exemple, SANS faire de comparaison comme vous l'annoncez, je serais bien curieux que vous m’indiquiez un code pour cela

[ToTo13]

Bonjour,

pas de soucis, voilà comment procéder sans comparaison :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
 - Déclarer un tableau T de quatre éléments et l'initialiser à 0
 
 - parcourir tous les élément "e" et incrémenter T en faisant T[e]++ ;
 
 - Dans l'exemple que tu as donné, on obtient alors comme contenu de T :
    1 1 1 1
 
 - Il suffit alors de restituer les éléments qui sont dans T
    - Pour i qui va de 1 à Taille de T
          tant que T[i] est non nul
                 Afficher i
                 T[i]--

Si on prend un autre exemple : 3 2 1 2, T sera rempli de la sorte :
T = 1 2 1
Donc on le vide en mettant :
1 2 2 3


C'est le tri le plus rapide qu'il existe, il est en O(N), plus exactement en O(2N), mais on se fout des coéfficients dans la complexité.
Le quicksort est en MOYENNE, le tri par COMPARAISON le plus rapide.

[j.p.mignot]

Il y a une comparaison à 0 ( ou eventuellement valeur min suivant la construction de T )??

[Jean-Marc.Bourguet]

Bonjour,

pas de soucis, voilà comment procéder sans comparaison :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
 - Déclarer un tableau T de quatre éléments et l'initialiser à 0
 
 - parcourir tous les élément "e" et incrémenter T en faisant T[e]++ ;
 
 - Dans l'exemple que tu as donné, on obtient alors comme contenu de T :
    1 1 1 1
 
 - Il suffit alors de restituer les éléments qui sont dans T
    - Pour i qui va de 1 à Taille de T
          tant que T[i] est non nul
                 Afficher i
                 T[i]--

Si on prend un autre exemple : 3 2 1 2, T sera rempli de la sorte :
T = 1 2 1
Donc on le vide en mettant :
1 2 2 3


C'est le tri le plus rapide qu'il existe, il est en O(N), plus exactement en O(2N), mais on se fout des coéfficients dans la complexité.
Le quicksort est en MOYENNE, le tri par COMPARAISON le plus rapide.

Tu supposes également que ton espace de valeur est suffisemment densément peuplé d'une part et que tu peux allouer suffisemment de mémoire en plus d'autre part.

[ToTo13]

Peux tu détailler, j'ai pas tout compris !!!

[Jedai]

C'est le tri le plus rapide qu'il existe, il est en O(N), plus exactement en O(2N), mais on se fout des coéfficients dans la complexité.
Le quicksort est en MOYENNE, le tri par COMPARAISON le plus rapide.

Ce tri est rarement le plus rapide : il n'est le plus rapide que si tu as un espace de valeur possible suffisamment petit, sinon il est inutilisable (ou extrèmement lent). Par exemple si le min est -2*10^9 et le max 2*10^9 sur les entiers, ce tri sera extrèmement couteux...

Le quicksort n'est pas en moyenne le tri par comparaison le plus rapide, il fait partie des tris en moyenne en O(n log n) (comme le tri fusion et le tri par tas par exemple), et O(n log n) est la limite absolue pour les tris par comparaison, on ne peut pas faire plus rapide... Le tri fusion est théoriquement plus rapide que le quicksort en moyenne et en plus conserve une complexité en O(n log n) dans le pire cas (alors que quicksort dégènère en O(n²)), mais même le tri fusion n'est pas aussi rapide que le meilleur tri par comparaison, c'est facile à vérifier en créant soi-même ce tri pour de petites valeurs de n : le tri fusion fait quelques comparaisons inutiles.

--
Jedaï

[j.p.mignot]

D'autre part si on veut classer des entités non entières, il y a un réel problème. D'où je pense la remarque de Jean-Marc.Bourguet. Avec des rationnels c'est envisageable à grands frais sur la taille de T mais avec des irrationnels cela devient problématique de définir le "zoom" nécessaire pour le classement.

[Jean-Marc.Bourguet]

Peux tu détailler, j'ai pas tout compris !!!

Tu as besoin d'un tableau supplémentaire. Ce peut être génant.

Ton algo n'est pas seulement en O(N), il est aussi en O(max-min). Et si N log N < max-min il n'est pas "meilleur" (pour autant que la complexité assymtotique ait réellement un intérêt pratique pour les données en question, ce dont il faut toujours s'assurer avant de faire un choix d'algo sur cette base).

Sur le même principe il y a aussi le radix-sort.