tri

Version imprimable

16/03/2006, 18h50
sidahmed

tri

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

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

Code:

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;

16/03/2006, 21h15
Rafy

Hum aller voir la FAQ... :twisted:
16/03/2006, 23h40
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?
17/03/2006, 07h38
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
17/03/2006, 09h14
Jean-Marc.Bourguet

Citation:

Envoyé par 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

http://www.cs.vu.nl/~dick/gnomesort.html
17/03/2006, 10h20
pcaboche

Citation:

Envoyé par j.p.mignot

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 !
17/03/2006, 10h27
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
17/03/2006, 13h46
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ï
17/03/2006, 14h36
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é.
17/03/2006, 17h04
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
19/03/2006, 09h17
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.
19/03/2006, 09h56
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

Bonjour,

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

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.

19/03/2006, 10h19
j.p.mignot

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

Citation:
Envoyé par ToTo13
Bonjour,

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

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.

19/03/2006, 10h42
ToTo13

Peux tu détailler, j'ai pas tout compris !!!
19/03/2006, 12h37
Jedai

Citation:

Envoyé par ToTo13

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ï
19/03/2006, 13h14
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.
19/03/2006, 17h22
Jean-Marc.Bourguet

Citation:

Envoyé par ToTo13

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.
19/03/2006, 19h32
progfou

Au passage, puisqu'on parle de tri, je me demandais quel était le meilleur compromis temps/mémoire sur un grand nombre de données, pour des systèmes embarqués par exemple ?
19/03/2006, 20h45
Jean-Marc.Bourguet

Citation:

Envoyé par progman

Au passage, puisqu'on parle de tri, je me demandais quel était le meilleur compromis temps/mémoire sur un grand nombre de données, pour des systèmes embarqués par exemple ?

Les systèmes embarqués, ca recouvre beaucoup de choses et beaucoup de contraintes. Et par un "grand nombre de données" je vais supposer que tu veux dire "comportement quadratique inacceptable".

Un quicksort peut être bon mais a deux risques: si normalement il faut de la mémoire en log(N) en plus des données pour obtenir un temps en N log N avec une des meilleures constantes qui existe le comportement peut dégénéré et devenir linéaire en mémoire et quadratique en temps ce qui peut être un risque inacceptable.

Un heapsort a des avantages: en place avec une occupation constante en plus et un comportment N log N garanti même si la constante est moins bonne que le quick sort.

Puis il y a les algorithmes adaptatifs qui commencent comme un quicksort mais se terminent en heapsort s'ils détectent des données qui font dégénérer le quicksort. Mais l'implémentation est plus complexe.

Naturellement, si les données sont dans une liste chainée, un merge sort est quasiment imbattable: en place, comportement N log N en temps avec une constante faible qui peut dégénérer en comportement linéaire sur des données presque triées (ce que le heapsort ne fait pas mais le quicksort bien).
19/03/2006, 21h22
j.p.mignot

Je vois 2 problèmes de plus au quicksort
1- La récurrence ne permet pas de prévoir la quantité de stack qui va être nécessaire. Hors un problème à ce niveau induit inéluctablement une nécessité de reset voir reboot avec perte des données en cours. Le nombre de réentrances est entre autre fonction du choix du pivot ce qui est de loin pas facile à optimiser.
2- il n'est pas stable ( => si des éléments sont identiques au regard du test de comparaison ils peuvent tout de même être échangés ce qui peut poser dans certains cas des problèmes)

Il est tout de même en général plus rapide que tri par tas (heapsort) et je l’utilise de façon standard sur PC où la pile n’est pas réellement un problème ( pour mes applications ) mais l’évite sur les systèmes embarqués ( raison 1 ).
19/03/2006, 22h04
Jean-Marc.Bourguet

Citation:

Envoyé par j.p.mignot

Je vois 2 problèmes de plus au quicksort
1- La récurrence ne permet pas de prévoir la quantité de stack qui va être nécessaire. Hors un problème à ce niveau induit inéluctablement une nécessité de reset voir reboot avec perte des données en cours. Le nombre de réentrances est entre autre fonction du choix du pivot ce qui est de loin pas facile à optimiser.

C'est ce à quoi je faisais allusion en parlant de quantité de mémoire nécessaire pouvant être linéaire. Mais en fait il y a une astuce permettant d'y échapper.

Si on teste la taille des partitions, on peut faire d'abord la partition la plus petite et ensuite la partition la plus grande. Comme le tri de la partition la plus grande est un appel terminal (tail call), il peut être remplacé par une itération (soit par le compilateur, soit manuellement) et donc on n'a pas besoin de plus de O(log N) appels récursifs consommant de la pile. C'est toujours plus que pour le heapsort mais au moins on a une borne beaucoup plus raisonnable que le comportement linéaire.

Citation:

2- il n'est pas stable ( => si des éléments sont identiques au regard du test de comparaison ils peuvent tout de même être échangés ce qui peut poser dans certains cas des problèmes)

Si c'est un problème, heapsort n'est pas plus adapté. Si les données sont au départ dans un tableau, je ne vois pas d'algorithme en place avec un comportement N log N ou bien est-ce que je suis distrait?
19/03/2006, 22h12
j.p.mignot

Non le tri pas tas n'est pas stable non plu de ce point de vue. Par contre le 1er algorithme très simpliste que j'avais donné au début de cette discussion en réponse "méthode à une boucle" peu l'être si on trie avec "strictement inférieur" ou "strictement supérieur".
J’ai trouvé que le site
http://fr.wikipedia.org/wiki/Tri
avait pas mal d’informations

Citation:
Envoyé par ToTo13
Code:

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]--
Je crois que ce tri s'appelle le "pigeon-hole sort". Ca n'est applicable que sur les domaines finis, et avec peu de valeurs possibles.

***
Une fois, j'avais le problème suivant (c'était lors de mon stage de licence):
- on devait trier les informations contenues dans plusieurs gros fichiers
- en mémoire, on avait des objets qui indiquaient la position des données dans le fichier
- quand on avait besoin d'accéder aux données, on les rechargeait à partir du fichier

Donc quand on accédait aux données, ça mettait du temps vu qu'il fallait chercher l'info dans le fichier. En tant que stagiaire, je devais améliorer les performances de ce programme. Voilà ce que j'ai fait:
- je me suis fait un "cache" pour ne pas recharger systématiquement les données à partir du fichier

Par conséquent, si on accède plusieurs fois de suite aux mêmes données, on économise les temps de chargement et donc ça va plus vite. Il vaut mieux dans ce cas que l'algo effectue sur des données consécutives (éviter les aller-retour dans le fichier).

Voilà ce que ça donnait avec différents algos:
- tri par insertion (la méthode utilisée par l'ancien programme): performances misérables
- quick sort: bonne performances, mais pas si rapide que ça
- heap sort: très mauvaises performances (beaucoup trop d'aller-retour!)
- merge sort: les meilleures perfs. En plus, le tri est stable.

Si j'avais pu, j'aurais complètement repensé l'application en utilisant des flux pour le traitement plutôt que de mettre les données en mémoire pour les traiter après (parce que c'est franchement débile comme manière de faire...). Idem pour les tris: j'aurais fait un merge sort utilisant des fichiers temporaires. J'était même étonné qu'ils n'aient pas pensé à utiliser un SGBD pour faire ce genre de manip' (après tout, ils sont faits pour ça: traiter une grande quantié de données, et ils le font de manière optimale). Enfin bref, l'appli était mal pensée à la base mais j'ai dû faire avec. De toute façon, c'était une boite de m**** aussi...

Néanmoins, ce que je retire de cette "expérience", c'est que le "merge sort" a d'excellentes propriétés (bonne perfs, stable...) et qu'il permet une utilisation optimale du "cache" (utile quand les données ne sont pas toujours physiquement en mémoire mais qu'on doit les rechercher ailleurs: dans un fichier par exemple).