diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/algo/ft_bsearch.c | 24 | ||||
| -rw-r--r-- | src/algo/ft_mergesort.c | 29 |
2 files changed, 34 insertions, 19 deletions
diff --git a/src/algo/ft_bsearch.c b/src/algo/ft_bsearch.c index 8066479..5132fa2 100644 --- a/src/algo/ft_bsearch.c +++ b/src/algo/ft_bsearch.c @@ -6,7 +6,7 @@ /* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2020/02/10 05:29:05 by cacharle #+# #+# */ -/* Updated: 2020/02/10 05:43:18 by cacharle ### ########.fr */ +/* Updated: 2020/02/13 23:14:48 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ @@ -15,14 +15,18 @@ void *ft_bsearch(const void *base, size_t nel, size_t width, t_ftsearch_const *consts) { - void *found; + int res; + size_t mid; - if ((consts->compar)(consts->key, base + (nel / 2) * width) == 0) - return ((void*)base + (nel / 2) * width); - if ((found = ft_bsearch(base, nel / 2, width, consts)) != NULL) - return (found); - if ((found = ft_bsearch(base + (nel / 2) * width, nel - nel / 2, - width, consts)) != NULL) - return (found); - return (NULL); + if (nel < 1) + return (NULL); + mid = nel / 2; + res = (consts->compar)(consts->key, base + mid * width); + if (res == 0) + return ((void*)base + mid * width); + if (res < 0) + return (ft_bsearch(base, mid, width, consts)); + else + return (ft_bsearch(base + (mid + 1) * width, nel - mid - 1, + width, consts)); } diff --git a/src/algo/ft_mergesort.c b/src/algo/ft_mergesort.c index 5af248e..25b4255 100644 --- a/src/algo/ft_mergesort.c +++ b/src/algo/ft_mergesort.c @@ -6,7 +6,7 @@ /* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2020/02/10 02:26:41 by cacharle #+# #+# */ -/* Updated: 2020/02/10 02:59:10 by cacharle ### ########.fr */ +/* Updated: 2020/02/13 23:14:21 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ @@ -22,22 +22,31 @@ static int st_mergesort_error(void *left, void *right) static void st_merge_sorted(struct s_merge_sorted_arrays *arrays, size_t nel, size_t width, int (*compar)(const void *, const void *)) { + size_t bi; size_t li; size_t ri; + size_t mid; + mid = nel / 2; + bi = 0; li = 0; ri = 0; - while (li < nel / 2 && ri < nel - nel / 2) + while (li < mid && ri < nel - mid) { if (compar(arrays->left + li * width, arrays->right + ri * width) < 0) - ft_memcpy(arrays->base, arrays->left + li++ * width, width); + ft_memcpy(arrays->base + bi * width, + arrays->left + li++ * width, width); else - ft_memcpy(arrays->base, arrays->right + ri++ * width, width); + ft_memcpy(arrays->base + bi * width, + arrays->right + ri++ * width, width); + bi++; } - while (li < nel / 2) - ft_memcpy(arrays->base, arrays->left + li++ * width, width); - while (ri < nel - nel / 2) - ft_memcpy(arrays->base, arrays->right + ri++ * width, width); + while (li < mid) + ft_memcpy(arrays->base + bi++ * width, + arrays->left + li++ * width, width); + while (ri < nel - mid) + ft_memcpy(arrays->base + bi++ * width, + arrays->right + ri++ * width, width); } int ft_mergesort(void *base, size_t nel, size_t width, @@ -54,12 +63,14 @@ int ft_mergesort(void *base, size_t nel, size_t width, if ((arrays.right = malloc((nel - mid) * width)) == NULL) return (st_mergesort_error(arrays.left, NULL)); ft_memcpy(arrays.left, base, mid * width); - ft_memcpy(arrays.right, base, (nel - mid) * width); + ft_memcpy(arrays.right, base + mid * width, (nel - mid) * width); if (ft_mergesort(arrays.left, mid, width, compar) == -1) return (st_mergesort_error(arrays.left, arrays.right)); if (ft_mergesort(arrays.right, nel - mid, width, compar) == -1) return (st_mergesort_error(arrays.left, arrays.right)); arrays.base = base; st_merge_sorted(&arrays, nel, width, compar); + free(arrays.left); + free(arrays.right); return (0); } |