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 :
QUICKSORT
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
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); }
Et la maniere dont j'initialise mon tableau pour tester mes algos :
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
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); }
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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); }
Partager