Quicksort slower than mergesort...
-
I try to implement classical sorting algorithm, I do not understand why my quicksort is slower than my mergesort. I spend a lot of time trying to understand why. Do you have any idea ? For both :
#define ARRAY_INDEX(tab, i) ((void*)((char*)(tab) + (i) * type_size))
My mergesort :
void merge(void *tab, void *aux, int a, int b)
{
int i, j, k, mid;ft\_copy\_tab(tab, aux, a, b); mid = (a + b) / 2; i = a; j = mid + 1; k = a; while (k <= b) { if (i > mid) ft\_copy\_index(tab, aux, k, j++); else if (j > b) ft\_copy\_index(tab, aux, k, i++); else if (f\_cmp(ARRAY\_INDEX(aux, i), ARRAY\_INDEX(aux, j)) > 0) ft\_copy\_index(tab, aux, k, j++); else ft\_copy\_index(tab, aux, k, i++); k++; } return ;}
My quicksort :
void ft_quicksort(void *tab, int a, int b)
{
int i, lower, upper;if (a >= b) return ; lower = a; upper = b; i = a; while (i <= upper) { if (f\_cmp(ARRAY\_INDEX(tab, lower), ARRAY\_INDEX(tab, i)) > 0) { ft\_swap(tab, lower, i, type\_size); lower++; i++; } else if (f\_cmp(ARRAY\_INDEX(tab, lower), ARRAY\_INDEX(tab, i)) < 0) { ft\_swap(tab, i, upper, type\_size); upper--; } else ++i; } ft\_sort(tab, a, lower - 1); ft\_sort(tab, upper + 1, b);}
-
I try to implement classical sorting algorithm, I do not understand why my quicksort is slower than my mergesort. I spend a lot of time trying to understand why. Do you have any idea ? For both :
#define ARRAY_INDEX(tab, i) ((void*)((char*)(tab) + (i) * type_size))
My mergesort :
void merge(void *tab, void *aux, int a, int b)
{
int i, j, k, mid;ft\_copy\_tab(tab, aux, a, b); mid = (a + b) / 2; i = a; j = mid + 1; k = a; while (k <= b) { if (i > mid) ft\_copy\_index(tab, aux, k, j++); else if (j > b) ft\_copy\_index(tab, aux, k, i++); else if (f\_cmp(ARRAY\_INDEX(aux, i), ARRAY\_INDEX(aux, j)) > 0) ft\_copy\_index(tab, aux, k, j++); else ft\_copy\_index(tab, aux, k, i++); k++; } return ;}
My quicksort :
void ft_quicksort(void *tab, int a, int b)
{
int i, lower, upper;if (a >= b) return ; lower = a; upper = b; i = a; while (i <= upper) { if (f\_cmp(ARRAY\_INDEX(tab, lower), ARRAY\_INDEX(tab, i)) > 0) { ft\_swap(tab, lower, i, type\_size); lower++; i++; } else if (f\_cmp(ARRAY\_INDEX(tab, lower), ARRAY\_INDEX(tab, i)) < 0) { ft\_swap(tab, i, upper, type\_size); upper--; } else ++i; } ft\_sort(tab, a, lower - 1); ft\_sort(tab, upper + 1, b);}
Is your list already (partially) sorted? What element are you using for the pivot? Does your list have a lot of repeated elements? As for the data structures themselves, both take O(n log n) comparisons in the average case. In the worst case, quicksort takes O(n^2) comparisons, whereas mergesort takes O(n log n) comparisons.
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
-
Is your list already (partially) sorted? What element are you using for the pivot? Does your list have a lot of repeated elements? As for the data structures themselves, both take O(n log n) comparisons in the average case. In the worst case, quicksort takes O(n^2) comparisons, whereas mergesort takes O(n log n) comparisons.
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
My list is not sorted at all :
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);}
I have noticed that if I my list has a lot of duplicate keys ("tab[len] = rand()%10" instead of "tab[len] = rand()"), my quicksort is much faster than my mergesort. I use the first element for the pivot. I wanted to have consistent result first and then improve my mergesort. For instance, it takes 7 seconds or so for my mergesort to sort 10.000.000 integers and around 13sec for my quicksort (qsort from stdlib.h takes 4sec). Does that mean that my algo (without improvement) does not work well enough ?
-
My list is not sorted at all :
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);}
I have noticed that if I my list has a lot of duplicate keys ("tab[len] = rand()%10" instead of "tab[len] = rand()"), my quicksort is much faster than my mergesort. I use the first element for the pivot. I wanted to have consistent result first and then improve my mergesort. For instance, it takes 7 seconds or so for my mergesort to sort 10.000.000 integers and around 13sec for my quicksort (qsort from stdlib.h takes 4sec). Does that mean that my algo (without improvement) does not work well enough ?
If your implementation "only" takes about 3 times as long as the stdlib qsort, then you can be reasonably sure that, technically, you did it correctly. As for why your program takes longer, there are quite a number of things that can go wrong in performance optimization. A good start would be avoiding shortcuts and explicit optimization, even if it may sound counter-intuitive. The compiler is exceptionally good at optimizing code without your help, but to do this efficiently, it needs to see the "real" code, not some byte manipulation that it can't make heads or tails of. One example is your #define: all it does is accessing array members, but all the compiler sees is some weird pointer arithmetic. Do leave the compiler arithmetic to the compiler, and you'll find that at the very least you'll get more readable code at no performance loss, and maybe you'll even see an improvement. I think I understand what you use this define for, but if I'm right, all you really need is a typecast from void* to int* (or pointer to whatever element type you're using) Another issue may be the various helper functions you're calling: without the actual type information, these functions may be very inefficient. E. g. a function to swap two ints only requires a handful of assembler instructions. A function to swap two arrays of n bytes, where n is a run time variable, requires about three to five times as much. You could check your compiler's aqssembler output to see what it makes of your code. Try different variants to find out what the compiler makes of it. Maybe that can give you some insight into what is causing the performance issue.
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
-
If your implementation "only" takes about 3 times as long as the stdlib qsort, then you can be reasonably sure that, technically, you did it correctly. As for why your program takes longer, there are quite a number of things that can go wrong in performance optimization. A good start would be avoiding shortcuts and explicit optimization, even if it may sound counter-intuitive. The compiler is exceptionally good at optimizing code without your help, but to do this efficiently, it needs to see the "real" code, not some byte manipulation that it can't make heads or tails of. One example is your #define: all it does is accessing array members, but all the compiler sees is some weird pointer arithmetic. Do leave the compiler arithmetic to the compiler, and you'll find that at the very least you'll get more readable code at no performance loss, and maybe you'll even see an improvement. I think I understand what you use this define for, but if I'm right, all you really need is a typecast from void* to int* (or pointer to whatever element type you're using) Another issue may be the various helper functions you're calling: without the actual type information, these functions may be very inefficient. E. g. a function to swap two ints only requires a handful of assembler instructions. A function to swap two arrays of n bytes, where n is a run time variable, requires about three to five times as much. You could check your compiler's aqssembler output to see what it makes of your code. Try different variants to find out what the compiler makes of it. Maybe that can give you some insight into what is causing the performance issue.
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
-
If your implementation "only" takes about 3 times as long as the stdlib qsort, then you can be reasonably sure that, technically, you did it correctly. As for why your program takes longer, there are quite a number of things that can go wrong in performance optimization. A good start would be avoiding shortcuts and explicit optimization, even if it may sound counter-intuitive. The compiler is exceptionally good at optimizing code without your help, but to do this efficiently, it needs to see the "real" code, not some byte manipulation that it can't make heads or tails of. One example is your #define: all it does is accessing array members, but all the compiler sees is some weird pointer arithmetic. Do leave the compiler arithmetic to the compiler, and you'll find that at the very least you'll get more readable code at no performance loss, and maybe you'll even see an improvement. I think I understand what you use this define for, but if I'm right, all you really need is a typecast from void* to int* (or pointer to whatever element type you're using) Another issue may be the various helper functions you're calling: without the actual type information, these functions may be very inefficient. E. g. a function to swap two ints only requires a handful of assembler instructions. A function to swap two arrays of n bytes, where n is a run time variable, requires about three to five times as much. You could check your compiler's aqssembler output to see what it makes of your code. Try different variants to find out what the compiler makes of it. Maybe that can give you some insight into what is causing the performance issue.
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
-
I try to implement classical sorting algorithm, I do not understand why my quicksort is slower than my mergesort. I spend a lot of time trying to understand why. Do you have any idea ? For both :
#define ARRAY_INDEX(tab, i) ((void*)((char*)(tab) + (i) * type_size))
My mergesort :
void merge(void *tab, void *aux, int a, int b)
{
int i, j, k, mid;ft\_copy\_tab(tab, aux, a, b); mid = (a + b) / 2; i = a; j = mid + 1; k = a; while (k <= b) { if (i > mid) ft\_copy\_index(tab, aux, k, j++); else if (j > b) ft\_copy\_index(tab, aux, k, i++); else if (f\_cmp(ARRAY\_INDEX(aux, i), ARRAY\_INDEX(aux, j)) > 0) ft\_copy\_index(tab, aux, k, j++); else ft\_copy\_index(tab, aux, k, i++); k++; } return ;}
My quicksort :
void ft_quicksort(void *tab, int a, int b)
{
int i, lower, upper;if (a >= b) return ; lower = a; upper = b; i = a; while (i <= upper) { if (f\_cmp(ARRAY\_INDEX(tab, lower), ARRAY\_INDEX(tab, i)) > 0) { ft\_swap(tab, lower, i, type\_size); lower++; i++; } else if (f\_cmp(ARRAY\_INDEX(tab, lower), ARRAY\_INDEX(tab, i)) < 0) { ft\_swap(tab, i, upper, type\_size); upper--; } else ++i; } ft\_sort(tab, a, lower - 1); ft\_sort(tab, upper + 1, b);}
here is answer https://sourceforge.net/projects/pwwhashmap/files/?source=navbar[^]