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