Discussion :

[fpasquer]

Bonjour a tous,

Pour un de mes projets de cours, je dois trier des tableaux de pleins de façon diffèrent. Bien sûr avec qsort de stdlib c'est facile, mais je n'y ai pas le droit

Je viens donc de recoder mon propre qsort. Il fonctionne bien, mais je pense qu'il n’est pas au top de son optimisation (le malloc au début ).


Voici le code :

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
static void					*get_tmp(size_t width)
{
	static void				*tmp = NULL;
 
	if (tmp == NULL)
		tmp = ft_memalloc(width); // malloc + bzero
	return (tmp);
}
 
static void					switch_value(void *left, void *right, size_t width)
{
	void					*tmp;
 
	if ((tmp = get_tmp(width)) == NULL)
		return ;
	ft_memcpy(tmp, right, width); // like memcpy
	ft_memcpy(right, left, width);
	ft_memcpy(left, tmp, width);
}
 
static void					del_tmp(void)
{
	void					*tmp;
 
	if ((tmp = get_tmp(0)) != NULL)
		ft_memdel((void**)&tmp); // free and ptr = NULL
}
 
void						loop_qsort(void *base, size_t nel, size_t width,
		int (*compar)(const void *, const void *))
{
	void					*pivot;
	void					*end;
	void					*right;
	void					*left;
 
	end = (void*)base + (nel - 1) * width;
	right = end;
	left = base;
	pivot = base;
	if (nel <= 1 || width <= 0 || end < base)
		return ;
	while (left < right)
	{
		while (left < right && compar(pivot, right) < 0)
			right = (void*)right - width;
		switch_value(left, right, width);
		pivot = right;
		while (left < right && compar(pivot, left) >= 0)
			left = (void*)left + width;
		switch_value(left, right, width);
		pivot = left;
	}
	loop_qsort(base, (left - base) / width, width, compar);
	loop_qsort((void*)left + width, (end - left) / width, width, compar);
}
 
void						ft_qsort(void *base, size_t nel, size_t width,
		int (*compar)(const void *, const void *))
{
	if (nel <= 1)
		return ;
	loop_qsort(base, nel, width, compar);
	del_tmp();
}

Pouvez-vous me donner vos avis dessus svp ? et si vous voyez des erreurs je suis dispo

[Matt_Houston]

Puisque tu n'emploies ni VLA, ni alloca, je suppose que tu as la contrainte du C89/C90..

Ton buffer déclaré static en revanche n'est pas une super idée : ça rend l'ensemble non réentrant pour pas grand chose (il est aisé d'y remédier).

Je n'ai pas testé le programme ni lu son code en détail mais il me paraît correct sinon.

[fpasquer]

Bonsoir Matt_Houston, merci pour ta réponse.

Puisque tu n'emploies ni VLA, ni alloca, je suppose que tu as la contrainte du C89/C90..

Oui je dois compiler en C89 .

Ton buffer déclaré static en revanche n'est pas une super idée : ça rend l'ensemble non réentrant pour pas grand-chose (il est aisé d'y remédier).

J'ai une contrainte que j'ai oublié de préciser. A mon école, je ne peux pas avoir une fonction qui attend plus de 4 paramètres. Apres je peux utiliser une globale static, mais je n'aime pas trop ca ... Après pour moi il restait que cette option... Je me trompe ?

Il y a une chose que je trouve vraiment étrange et que je n'arrive pas à expliquer... Pour sort 1million de int random le vrai qsort a besoin d'environ 0,24 seconde. Moi il me faut 0.65 secondes

Avez-vous une idée d'où peut venir cette diff ?

Merci

[Matt_Houston]

J'ai une contrainte que j'ai oublié de préciser. A mon école, je ne peux pas avoir une fonction qui attend plus de 4 paramètres. [...] Après pour moi il restait que cette option... Je me trompe ?

Règle à la con IMHO, enfin.. soit. Tu peux éventuellement swap sans buffer auxiliaire. Autrement, en conservant l'implémentation récursive et sans malloc à chaque niveau, tu n'as pas vraiment le choix effectivement.

Apres je peux utiliser une globale static, mais je n'aime pas trop ca ...

Intrinsèquement c'est identique à ce que tu as fait là.

Il y a une chose que je trouve vraiment étrange et que je n'arrive pas à expliquer... Pour sort 1million de int random le vrai qsort a besoin d'environ 0,24 seconde. Moi il me faut 0.65 secondes

Avez-vous une idée d'où peut venir cette diff ?

Rien d'inquiétant, et c'est bon signe concernant l'implémentation du langage sur ta machine j'ai envie de dire, car les routines de base sont sensées être optimisées pour leur environnement.. Garde également en mémoire que malgré son nom, qsort ne permet en aucun cas de préjuger de la nature des algorithmes utilisés pour la réalisation du tri. En témoigne la note sur cppreference :

Despite the name, neither C nor POSIX standards require this function to be implemented using quicksort or make any complexity or stability guarantees.

On peut très bien imaginer qu'une implémentation opte pour le tri par insertion pour une quantité de données relativement restreinte, jusqu'à un certain seuil, puis bascule sur un tri fusion, etc..