Tri

[Morpheus]

Salut,

quels sont les différents algos disponibles pour faire un tri de tableaux ?

Merci

[Morpheus]

Cette méthode doit parcourir un texte en cherchant le pattern et renvoit un Iterable.

Cette méthode servira à pouvoir avoir une autre méthode :

Code: Tout sélectionner

public Iterable et(Iterable iterable1, Iterable iterable2)

permettant de récupérer les mots satisfaisant 2 conditions

Je ne sais pas si je suis clair ...

Quelqu'un aurait'il une idée sur la manière de procéder ?

[nox]

ola y en a un paquet : tri par insertion, tri optimisé, tri bulle etc...

pour les algos en details (en C en l'occurence) : http://fr.wikipedia.org/wiki/Tri

[nameless]

je te conseille ce site :
http://www.dailly.info/algorithmes-de-tri/bulle.php
il recence bcp de methode de tri en calculant leurs complexités

[buzard]

Bonjour,

Le plus simple pour du tri sur tableau c'est le tri rapide sur place, c'est la methode courament utilisé et qui ne varie que tres peut en complexité surtout lorsque le pivot est bien choisi.

en général, on se contente de prendre un élément particulier (premier element du tableau, ou dernier), mais cela donne une complexité linéaire dans le pire des cas (lorsque le tableau est déjà trié). Sinon un bon moyen c'est de choisir un pivot au hasard, ou encore mieux de choisir parmis trois candidat celui qui est au milieu. Ainsi tu répartie encore mieux la charge.

de toute manière cela te donne une complexité en O(n.ln(n)) trés satisfaisante. Tous les autres tris c'est de la pacotille à côté. Sauf peut etre le trie shell, lorsque tu doit traiter d'enorme quantité de données.

Seul hic, si tu veut conserver l'ordre d'occurence des éléments égaux (en cas de structure plus complexe que des entiers), cela demande un peut plus de calcul, mais le surcout est amortie si tu part du principe qu'il y en a pas beacoup.

Voila l'algo écrit en C (avec un tableau d'entier, et un choix de pivot tres simple) :

Code: Tout sélectionner

void tri_rapide (int T[], int i, int j)
{
   // pour s'arreter
   if (j-i < 2) return;
   
   // on separe le tableau en deux
   int k = pivot(T, i, i, j);

   // puis on tri chaque partie
   tri_rapide(T, i, k);
   tri_rapide(T, k+1, j);
}

int pivot (int T[], int i, int k, int j)
{
   // on place le pivot en tete
   int x = T[k];
   T[k] = T[i];
   k = i;
   
   // on transfert tous les éléments plus petit à sa gauche
   while (++i < j) { if (T[i] < x)
   {
         T[k] = T[i];
         k++;
         T[i] = T[k];
   }}
   T[k] = x;
   
   // puis on renvoie la position final du pivot
   return k;
}


[Chimomo]

Le tri rapide n'est pas le seul à avoir une complexité quasi-linéaire, il y en a bien d'autres comme le tri fusion par exemple qui marche très bien (pour le tri par bulles je ne me souviens pas de la complexité) ou le tri par tas bien qu'ils soient surement plus faciles à implémenter sur des listes.

[buzard]

Le tri rapide n'est pas le seul à avoir une complexité quasi-linéaire, il y en a bien d'autres comme le tri fusion par exemple qui marche très bien (pour le tri par bulles je ne me souviens pas de la complexité) ou le tri par tas bien qu'ils soient surement plus faciles à implémenter sur des listes.

Oui d'accord mais, ils sont nombreux, mais le tri rapide est quand meme plus efficace. On place un element à chaque récursion de facon définitif. Apres il a plus une gueule de récursif terminal (c'est pas vrai, car il a deux appels, mais ils sont releguer à la fin au moins).

Le tri fusion est, il est vrai, moins sensible aux données, la complexité y est toujours n.ln(n), mais un bon choix de pivot résorbe se problème avec le tri rapide. Le tri fusion requiert egalement plus de place, il vaut mieux un deuxieme tableau. Si on tente la fusion sur place, on est confronté à des problèmes de décalage de bloc de tableau. Finallement on y perd en efficacité (il est vraiment plus adapté aux listes)

Le tri bulle c'est de la daube O(n^2) en moyenne, bref pas d'interet à moins que le tableau soit déjà presque trié, dans quel cas ca peut servir.

l'avantage du tri rapide, c'est qu'il est possible de le rendre itératif, ainsi on fais vraiment du sur place, sans utiliser de pile de récursion. Bref il a vraiment tous pour plaire.

Souvent on l'utilise pour des tailles suffisantes de donnée, et pour les tableaux plus petit, un simple tri par selection est souvent utilisé (n<20 ou 30)

Sinon le seul concurent du tri rapide, c'est le tri par tas, qui garantie un pire des cas en O(n ln n), mais il est plus lent (d'un facteur 2 a peu près) mais il n'utilise pas de récursivité.

Et le meilleur algo c'est un hybride de tous ca. il commence avec le tri rapide, puis au dela d'une certaine profondeur bascule au tri tas ou au tri par selection si le sous-tableau est assez petit. Les parametres de commutation, dépendent évidemment des données, pour etre vraiment optimal.

[Chimomo]

En effet il semble que le plus efficace serait un algorithme qui étudie d'abord le tableau à trier puis chois le tri a effectuer ainsi les appels récursifs ne se font pas tous avec le même tri. Mais si on fait un calcul de complexité en moyenne, la complexité restera O(n.ln(n)) (mais un calcul exact (ce qui serait à mon avis assez difficile), permettrait de voir l'intérêt par rapport aux autres)

[Dark-Water]

Le plus simple pour du tri sur tableau c'est le tri rapide sur place,

heu je suis pas d'accord le plus simple à implémenter est le tri à bulles mais certes il n'est pas efficace de complexité si je me rappelle bien O(n^n) mais si tu doit trier de petit tableau de quelques milliers d'élèment le tri à bulles suffit car compte tenu de la puissance des machines la différence entre tri a bulles et tri rapide est invisible.
Le tri à bulles sera plus rapide à implementer tu as moins de chances de faire des erreurs.

Inutile de prendre des algos optimisé et complexe quand on a peu de données à traiter

Analogie : Pas besoin de prendre une grue de chantier pour soulever un pack de bouteille d'eau :we:

[Chimomo]

n^n ca me parait beaucoup (pour 1000 éléments ca fait déja 10^3000 opérations, sur un bon compliateur t'en a pour plus de 10^2980 années !!!!!!!!!!!!!!!

[Dark-Water]

tu a raison c plutot n² car tu parcours au premier coup n fois puis n-1 etc ... c donc somme de i=0 à n de i = n(n-1)/2 donc n²

Désolé jt pas réveillé ce matin :we:

[Chimomo]

c bien ce que je me disais lol