Fused | Merci de vos messages, j'ai réussi à trouver ou celà bloque, en fait je test plusieurs tri différents, cela bloque sur le tri rapide quand je lui balance un tableau déjà trié, le temps est de l'ordre de 60 secondes pour 100 000 éléments, contre environ 0.6 secondes pour le même tableau non trié !
Je dois avoir une erreur forcément ! mais je ne trouve pas du tout !
Je vous donne un extrait du code, ce qui sert là ou ça plante :
Code :
- int main (int argc, char** argv)
- {
- int n = 100000; // Nombre d'éléments à trier au départ
- int t_rapide[n]; // Tableau pour le tri rapide
- int t_tas[n+1]; // Tableau pour le tri par tas
- int t_trie[n]; // Tableau trié du sauvegarde
- for (int z=1; z<=4; z++)
- // Cette boucle permet de varier les 4 types de tableau d'entrée
- // 1. Tableau aléatoire
- // 2. Tableau trié
- // 3. Tableau partiellement trié
- // 4. Tableau quasiment trié
- {
- switch (z)
- {
- case 1 :
- // Tableaux aléatoires
- ...
- case 2 :
- // Tableaux triés
- copie_tableau(t_rapide, t_tas, 1, n+1);
- // je copie le tableau en double exemplaire pour le trier en tri rapide puis en tri par tas
- break;
- case 3 :
- // Tableaux partiellement triés
- ...
- case 4 :
- // Tableaux quasiment triés
- ...
- default :
- break;
- }
- for (int t=0; t<2; t++)
- {
- temps_initial = clock ();
- if (t==0) tri_rapide(t_rapide,0,n-1); // ici cela met 58 secondes à n=100 000 et z = 2
- else tri_tas(t_tas,1,n);
- temps_final = clock ();
- temps_cpu = (temps_final - temps_initial) * 1e-6;
- }
- }
- }
|
Voilà, en k = 2, j'ai déjà le tableau t_rapide déjà trié du coup d'avant, je le retrie et cela est très long, même tandis que tous les autres tris fonctionnent rapidement.
edit : je rajoute l'algo de tri rapide :
Code :
- int partition(int T[],int p,int s)
- {
- int x = T[s];
- int i = p-1;
- for(int j = p ; j < s; j++)
- {
- if(T[j]<= x)
- {
- i++;
- int temp = T[i];
- T[i] = T[j];
- T[j] = temp;
- }
- }
- int temp = T[i+1] ;
- T[i+1] = T[s] ;
- T[s] = temp;
- return i+1;
- }
- void tri_rapide(int tab[],int p,int n)
- {
- if(p < n)
- {
- int q = partition(tab,p,n);
- tri_rapide(tab,p,q-1);
- tri_rapide(tab,q+1,n);
- }
- }
|
Quand j'interompt l'execution avec gdb lorsque qu'il bloque, je suis dans la boucle for entre les lignes 5 à 14 ici.
Je reste sur mon PC tant que j'ai pas trouvé, faut que je lance l'algo cette nuit pour faire des tests en boucle pour un rendu lundi, si vous avez la bonté de m'aider, c'est avec très grand plaisir !
Je peux donner plus de code si il faut, voir tout le source si besoin est.
Merci beaucoup d'avance ! Message édité par Fused le 16-12-2007 à 01:16:31
|