Discussion :

[Vinzius]

Yip all

Bon alors j'ai un petit problème avec l'algo de tri rapide que je code. Pour un tableau à 1 million de case ca marche, mais pour 10 million ca me sort seg fault => donc il accède à un endroit ou il devrait pas ...
Mais bon entre un tab à 1 million et 10 million d'éléments...

Enfin voici mon code, qu'en pensez-vous :

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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
void tab_affiche(int tab[], int taille) {
int n;
	for (n=0;n<taille;n++)
		printf("%d ",tab[n]);
	printf("\n");
}
 
 
int tri_rapide_repartir(int tab[], int deb, int fin) {
int i,deb_tri=deb,pivot=tab[deb];
 
	for (i=deb+1;i<=fin;i++)
		if (tab[i]<pivot) {
			deb_tri++;
			permuter_tab(tab,deb_tri,i);
		}
 
	permuter_tab(tab,deb_tri,deb);
 
return deb_tri;
}
 
void tri_rapide_aux(int tab[], int deb, int fin) {
int pivot;
 
	if (deb<fin) {
		pivot=tri_rapide_repartir(tab,deb,fin);
		tri_rapide_aux(tab,deb,pivot-1);
		tri_rapide_aux(tab,pivot+1,fin);
	}
 
}
 
void tri_rapide(int tab[], int taille) {
	tri_rapide_aux(tab,0,taille-1);
}

Merci de votre aide

[Emmanuel Delahaye]

Bon alors j'ai un petit problème avec l'algo de tri rapide que je code. Pour un tableau à 1 million de case ca marche, mais pour 10 million ca me sort seg fault => donc il accède à un endroit ou il devrait pas ...
Mais bon entre un tab à 1 million et 10 million d'éléments...

Enfin voici mon code, qu'en pensez-vous :

Code :

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

1
2
3
4
 
void tri_rapide(int tab[], int taille) {
	tri_rapide_aux(tab,0,taille-1);
}

La récursion, c'est mal...

[Gruik]

(Tiens, un collegue a écrit exactement le meme code (a part le nom des fonctions et variables), ça doit etre un algo courant)

[Vinzius]

La récursion, c'est mal...

Si tu me propose une autre solution ej veux bien t'écouter pour la tenter

[Trap D]

(Tiens, un collegue a écrit exactement le meme code (a part le nom des fonctions et variables), ça doit etre un algo courant)

C'est le quick sort, rien d'extraordinaire !!

[Emmanuel Delahaye]

La récursion, c'est mal...

Si tu me propose une autre solution ej veux bien t'écouter pour la tenter

-> forum "Algorithmes"

[HanLee]

Bon alors j'ai un petit problème avec l'algo de tri rapide que je code. Pour un tableau à 1 million de case ca marche, mais pour 10 million ca me sort seg fault => donc il accède à un endroit ou il devrait pas ...
Mais bon entre un tab à 1 million et 10 million d'éléments...

Enfin voici mon code, qu'en pensez-vous :

Code :

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

1
2
3
4
 
void tri_rapide(int tab[], int taille) {
	tri_rapide_aux(tab,0,taille-1);
}

La récursion, c'est mal...

Seulement si on fait pas gaffe à ce qu'on fait...

[gege2061]

La récursion, c'est mal...

Si tu me propose une autre solution ej veux bien t'écouter pour la tenter

Dérécursification

La récursion, c'est mal...

Seulement si on fait pas gaffe à ce qu'on fait...

Pour savoir ce que l'on fait, il faudrait pouvoir éviter un débordement de la pile... bon courrage !

[Trap D]

le fait de dérécursifier peut peut-être faire perdre l'intérèt du quick sort.

[HanLee]

La récursion, c'est mal...

Si tu me propose une autre solution ej veux bien t'écouter pour la tenter

Dérécursification

La récursion, c'est mal...

Seulement si on fait pas gaffe à ce qu'on fait...

Pour savoir ce que l'on fait, il faudrait pouvoir éviter un débordement de la pile... bon courrage !

On ne déborde pas la pile avec le quicksort parce que la taille des données est telle que quand tu le logarithmes, c'est rien du tout ; et on choisit un pivot au pif de préférence, pour éviter de se trouver dans un cas dégénéré (en O(n²) ).