A voir également:
- Tri
- Comment faire un tri personnalisé sur excel - Guide
- Logiciel tri photo - Guide
- Tri turf - Télécharger - Sport
- Votre colis est retenu au centre de tri - Accueil - Arnaque
- Wap tri - Télécharger - Divers TV & Vidéo
6 réponses
Comment ça pas toujours ? le quicksort pas toujours simple et rapide tu veux dire ? Je pensais la réponse adéquate vu que Lili est probablement débutante, et le quicksort présent la plupart du temps dans les fonctions du compilateurs... Sinon, il faut le dire, y'a beaucoup mieux pour faire du tri efficace, mais c'est plus compliqué...
Pour trier une centaine d'entrée une fois, tu fais un bubblesort ^^
Pour trier des millions d'entrées, tu fais du calcul parallèle sur un réseau papillon
Et entre les deux y a le choix ;-)
Je pense que si quicksort est le plus utilisé dans les implémentations c'est parce qu'il est peu gourmand en ressource, contrairement au tri par fusion par exemple qui utilise deux fois la mémoire initiale du tableau pour faire le calcul.
D'ailleurs dans le lien de JooS, les statistiques sont en nombre d'écritures+comparaisons, habituellement quand on parle de complexité, on évalue théoriquement le nombre de comparaisons pour le pire des cas, et les résultats seraient légèrement différents. D'ailleurs ici on ne sait pas trop dans ces stats comment sont les tableaux avant le tri (triés, presque triés, triés à l'envers...) certains tris sont meilleurs si on est dans un certain type de configuration, et il faut savoir profiter de ces avantages.
Pour trier des millions d'entrées, tu fais du calcul parallèle sur un réseau papillon
Et entre les deux y a le choix ;-)
Je pense que si quicksort est le plus utilisé dans les implémentations c'est parce qu'il est peu gourmand en ressource, contrairement au tri par fusion par exemple qui utilise deux fois la mémoire initiale du tableau pour faire le calcul.
D'ailleurs dans le lien de JooS, les statistiques sont en nombre d'écritures+comparaisons, habituellement quand on parle de complexité, on évalue théoriquement le nombre de comparaisons pour le pire des cas, et les résultats seraient légèrement différents. D'ailleurs ici on ne sait pas trop dans ces stats comment sont les tableaux avant le tri (triés, presque triés, triés à l'envers...) certains tris sont meilleurs si on est dans un certain type de configuration, et il faut savoir profiter de ces avantages.
Tout à fait d'accord^^. Dès qu'on souhaite trier de grosse quantitées en critères multiples, il est nécessaire d'exploiter plusieurs approches. En tant qu'amateur d'optimisation poussée, j'ai longuement muri ce sujet, et ce que j'ai trouvé de plus efficace ce fait en deux points :
- Evaluation d'une valeur grossière 16 bits compactée pour chaque entrée, pouvant être déterminée selon plusieurs clés, mais pas forcément toutes, tout en comptant le nombre d'entrées pour chaque valeur grossières,
Repositionnement direct des entrées en fonction de chaque valeur approchée. A ce stade on trouve de gros blocs d'entrées correctement positionnés, mais anarchiques en leur sein.
- Si le nombre d'entrées reste important, on recommence en approfondissant les critères de clés, sinon utilisation d'un quicksort modifié, positionnant les valeurs supérieures, inférieures ET égales au pivot de comparaison.
L'étape 'Quicksort' se fait de manière 'fenêtrée', le tri étant effectué jusqu'au bout uniquement là où le besoin est réel - la zone affichée par exemple-, grâce à un tableau de flags, déterminant les zones dans lesquelles le tri à été finalisé.
J'ai développée une unitée de 2500 lignes en assembleur à ce sujet, en testant différentes possibilitées, et celle-çi a donné les meilleurs résultats. J'obtiens un tri de 250000 fichiers (nom, taille, ext, etc...) en 80 ms en moyenne sur athlon 3500.
Après, pour un débutant qui souhaite juste réussir à trier un petit tableau, un quicksort peut convenir !
- Evaluation d'une valeur grossière 16 bits compactée pour chaque entrée, pouvant être déterminée selon plusieurs clés, mais pas forcément toutes, tout en comptant le nombre d'entrées pour chaque valeur grossières,
Repositionnement direct des entrées en fonction de chaque valeur approchée. A ce stade on trouve de gros blocs d'entrées correctement positionnés, mais anarchiques en leur sein.
- Si le nombre d'entrées reste important, on recommence en approfondissant les critères de clés, sinon utilisation d'un quicksort modifié, positionnant les valeurs supérieures, inférieures ET égales au pivot de comparaison.
L'étape 'Quicksort' se fait de manière 'fenêtrée', le tri étant effectué jusqu'au bout uniquement là où le besoin est réel - la zone affichée par exemple-, grâce à un tableau de flags, déterminant les zones dans lesquelles le tri à été finalisé.
J'ai développée une unitée de 2500 lignes en assembleur à ce sujet, en testant différentes possibilitées, et celle-çi a donné les meilleurs résultats. J'obtiens un tri de 250000 fichiers (nom, taille, ext, etc...) en 80 ms en moyenne sur athlon 3500.
Après, pour un débutant qui souhaite juste réussir à trier un petit tableau, un quicksort peut convenir !
le tri par sélection d'un tableau :
for (i=0; i<N-1; i++)
{
indice=i;
for (j=i+1; j<N; j++)
{
if (t[j]<t[indice])
indice=j;
}
tp=t[i];
t[i]=t[indice];
t[indice]=tp;
}
tri par insertion :
or (k=0; k<n; k++)
{
v=t[k];
i=k-1;
while (i>=0 && v<t[i])
{
t[i+1]=t[i];
i--;
}
t[i+1]=v;
}
tri par bull :
for (i=0;i<n;i++){
for (k=n-1; k>=i+1; k--){
if (t[k]<t[k-1]){
tp=t[k];
t[k]=t[k-1];
t[k-1]=tp;
}
}
}
bon courage :)
for (i=0; i<N-1; i++)
{
indice=i;
for (j=i+1; j<N; j++)
{
if (t[j]<t[indice])
indice=j;
}
tp=t[i];
t[i]=t[indice];
t[indice]=tp;
}
tri par insertion :
or (k=0; k<n; k++)
{
v=t[k];
i=k-1;
while (i>=0 && v<t[i])
{
t[i+1]=t[i];
i--;
}
t[i+1]=v;
}
tri par bull :
for (i=0;i<n;i++){
for (k=n-1; k>=i+1; k--){
if (t[k]<t[k-1]){
tp=t[k];
t[k]=t[k-1];
t[k-1]=tp;
}
}
}
bon courage :)
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question