Implementation mergesort / quicksort

Version imprimable

Bonjour a tous,

J'implemente les algorithmes de tri classiques pour m'entrainer. Je rencontre un probleme avec mon quicksort. Il fonctionne mais est plus lent que mon mergesort. (je n'ai optimise ni l'un ni l'autre pour le moment (insertionsort pour petit tableau, choix du pivot...), j'attends pour cela d'avoir des resultats coherents). Mon mergesort met 9 secondes pour trier 10.000.000 d'element, mon quicksort 14 (j'ai fait beaucoup de test et TOUS me donne cet ordre de grandeur). Mergesort est cependant sense etre plus rapide. J'ai longtemps cherche mais je ne vois absolument pas d'ou vient cet ecart. Si quelqu'un pouvait me donner des pistes de reflexion, ce serait genial, merci d'avance !

MERGESORT :

Code:

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdlib.h>
#include <string.h>
 
#define ARRAY_INDEX(tab, i) ((void*)((char*)tab + i * tosort.type_size))
 
typedef struct s_merge
{
	void	*tab;
	int	(*f_cmp)(const void*, const void*);
	int	type_size;
	int	last_index;
} t_merge;
 
void *ft_memalloc(size_t size)
{
	char *str;
	size_t i;
 
	if (!size)
		return (NULL);
	if (!(str = (char*)malloc(sizeof(char) * size)))
		return (NULL);
	i = -1;
	while (++i < size)
		str[i] = '\0';
	return ((void*)str);
}
 
static void ft_copy_tab(t_merge tosort, void *aux, int a, int b)
{
	void	*tab;
	void	*aux_start;
 
	aux_start = ARRAY_INDEX(aux, a);
	tab = ARRAY_INDEX(tosort.tab, a);
	memmove(aux_start, tab, (b - a + 1) * tosort.type_size);
}
 
static void ft_copy_index(t_merge tosort, void *aux, int i, int j)
{
	void *tab_i;
	void *aux_j;
 
	tab_i = ARRAY_INDEX(tosort.tab, i);
	aux_j = ARRAY_INDEX(aux, j);
	memmove(tab_i, aux_j, tosort.type_size);
}
 
static void merge(t_merge tosort, void *aux, int a, int b)
{
	int i, j, k;
	int mid;
 
	ft_copy_tab(tosort, aux, a, b);
	mid = (a + b) / 2;
	i = a;
	j = mid + 1;
	k = a;
	while (k <= b)
	{
		if (i > mid)
			ft_copy_index(tosort, aux, k, j++);
		else if (j > b)
			ft_copy_index(tosort, aux, k, i++);
		else if ((tosort.f_cmp)(ARRAY_INDEX(aux, i), ARRAY_INDEX(aux, j)) > 0)
			ft_copy_index(tosort, aux, k, j++);
		else
			ft_copy_index(tosort, aux, k, i++);
		k++;
	}
	return ;
}
 
static void ft_sort(t_merge tosort, void *aux, int a, int b)
{
	int mid;
 
	if (b <= a)
		return ;
	mid = (a + b) / 2;
	ft_sort(tosort, aux, a, mid);
	ft_sort(tosort, aux, mid + 1, b);
	merge(tosort, aux, a, b);
}
 
void ft_mergesort_array(void *tab, int (*f_cmp)(const void*, const void*), int type_size,
		int last_index)
{
	void *aux;
	t_merge tosort;
 
	tosort.tab = tab;
	tosort.f_cmp = f_cmp;
	tosort.type_size = type_size;
	tosort.last_index = last_index;
	if (!(aux = ft_memalloc(type_size * (last_index + 1))))
		return ;
	ft_sort(tosort, aux, 0, last_index);
}

QUICKSORT

Code:

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
66
#include <stdlib.h>
#include <string.h>
 
#define ARRAY_INDEX(tab, i) ((void*)((char*)(tab) + (i) * tosort.type_size))
 
typedef struct s_quick
{
	void	*tab;
	int	(*f_cmp)(const void*, const void*);
	int	type_size;
	int	last_index;
} t_quick;
 
static void ft_swap(t_quick tosort, int i, int j, int type_size)
{
	void	*tab_i;
	void	*tab_j;
	char	temp[type_size];
 
	tab_i = ARRAY_INDEX(tosort.tab, i);
	tab_j = ARRAY_INDEX(tosort.tab, j);
	memmove((void*)temp, tab_j, tosort.type_size);
	memmove(tab_j, tab_i, tosort.type_size);
	memmove(tab_i, (void*)temp, tosort.type_size);
}
 
static void ft_sort(t_quick tosort, int a, int b)
{
	int i, j, mid;
 
	if (a >= b)
		return ;
	i = a + 1;
	mid = a + 1;
	j = b;
	while (i <= j)
	{
		if (tosort.f_cmp(ARRAY_INDEX(tosort.tab, a), ARRAY_INDEX(tosort.tab, i)) > 0)
		{
			++mid;
			++i;
		}
		else if (tosort.f_cmp(ARRAY_INDEX(tosort.tab, a), ARRAY_INDEX(tosort.tab, i)) == 0)
			++i;
		else
		{
			ft_swap(tosort, i, j, tosort.type_size);
			--j;
		}
	}
	ft_swap(tosort, a, i - 1, tosort.type_size);
	ft_sort(tosort, a, i - 2);
	ft_sort(tosort, i, b);
}
 
void ft_quicksort_array(void *tab, int (*f_cmp)(const void*, const void*), int type_size,
	int last_index)
{
	t_quick	tosort;
 
	tosort.tab = tab;
	tosort.f_cmp = f_cmp;
	tosort.type_size = type_size;
	tosort.last_index = last_index;
	ft_sort(tosort, 0, last_index);
}

Et la maniere dont j'initialise mon tableau pour tester mes algos :

Code:

1
2
3
4
5
6
7
8
9
10
11
void *ft_init_array_int(int len)
{
	int *tab;
 
	srand(time(NULL));
	if (!(tab = (int*)malloc(len * sizeof(int))))
		return (NULL);
	while (len--)
		tab[len] = rand();
	return ((void*)tab);
}

20/02/2015, 17h57
gautgaut

C'est sans doute a cause du traitement des valeurs egales. Si je mets

Code:

tab[len] = rand()%10;

au lieu de

Code:

tab[len] = rand();

dans l'initialisation du tableau a trier, mon algo met des heures et des heures.

C'etait ca. Comme ca, c'est beaucoup mieux :

Code:

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
66
67
68
69
70
71
72
73
74
75
76
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
 
#define ARRAY_INDEX(tab, i) ((void*)((char*)(tab) + (i) * tosort.type_size))
 
typedef struct	s_quick
{
	void	*tab;
	int		(*f_cmp)(const void*, const void*);
	int		type_size;
	int		last_index;
}				t_quick;
 
static void		ft_swap(t_quick tosort, int i, int j, int type_size)
{
	void	*tab_i;
	void	*tab_j;
	char	temp[type_size];
 
	tab_i = ARRAY_INDEX(tosort.tab, i);
	tab_j = ARRAY_INDEX(tosort.tab, j);
	memmove((void*)temp, tab_j, tosort.type_size);
	memmove(tab_j, tab_i, tosort.type_size);
	memmove(tab_i, (void*)temp, tosort.type_size);
}
 
static void		ft_sort(t_quick tosort, int a, int b)
{
	int i, lower, upper;
 
	if (a >= b)
		return ;
	lower = a;
	upper = b;
	i = a;
	while (i <= upper)
	{
		if (tosort.f_cmp(ARRAY_INDEX(tosort.tab, lower), ARRAY_INDEX(tosort.tab, i)) > 0)
		{
			ft_swap(tosort, lower, i, tosort.type_size);
			lower++;
			i++;
		}
		else if (tosort.f_cmp(ARRAY_INDEX(tosort.tab, lower), ARRAY_INDEX(tosort.tab, i)) < 0)
		{
			ft_swap(tosort, i, upper, tosort.type_size);
			upper--;
		}
		else
			++i;
	}
	ft_sort(tosort, a, lower - 1);
	ft_sort(tosort, upper + 1, b);
/*	int t = -1;
	while (++t < 4)
			printf("%d\n",*(int*)(tosort.tab + 4 * t));
	printf("\n");
*/}
 
void			ft_quicksort_array(void *tab,
					int (*f_cmp)(const void*, const void*), int type_size,
						int last_index)
{
	t_quick	tosort;
 
/*	int i = -1;
	while (++i < 4)
			printf("%d\n",*(int*)(tab + 4 * i));
	printf("\n");
*/	tosort.tab = tab;
	tosort.f_cmp = f_cmp;
	tosort.type_size = type_size;
	tosort.last_index = last_index;
	ft_sort(tosort, 0, last_index);
}

20/02/2015, 21h35
gautgaut

Oui alors en fait ca ne marche bien que lorsqu'il y a peu de valeurs differentes (rand()%10)...
24/02/2015, 14h05
gangsoleil

Bonjour,

Avant de tester avec dix millions d'éléments, ne crois-tu pas que tu pourrais tester avec des tailles plus "raisonnables" ?

Ensuite, qsort n'est un bon algorithme que si le tableau n'est pas trié -- s'il est trié, l'algo est en n^2 si mes souvenirs sont bons.