aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/libft_algo.h32
-rw-r--r--include/libft_mem.h3
-rw-r--r--src/algo/ft_heapsort.c50
-rw-r--r--src/algo/ft_is_set.c5
-rw-r--r--src/algo/ft_mergesort.c65
-rw-r--r--src/algo/ft_qsort.c4
-rw-r--r--src/mem/ft_memswap.c12
7 files changed, 151 insertions, 20 deletions
diff --git a/include/libft_algo.h b/include/libft_algo.h
index 4dc3353..14496dd 100644
--- a/include/libft_algo.h
+++ b/include/libft_algo.h
@@ -6,27 +6,41 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/19 07:22:57 by cacharle #+# #+# */
-/* Updated: 2020/02/10 02:21:47 by cacharle ### ########.fr */
+/* Updated: 2020/02/10 03:04:17 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
#ifndef LIBFT_ALGO_H
# define LIBFT_ALGO_H
-typedef int t_bool;
+# include <stdlib.h>
+# include <stddef.h>
+# include "libft_mem.h"
+# include "libft_types.h"
typedef struct
{
- int lo;
- int hi;
-} t_ftrange;
+ int lo;
+ int hi;
+} t_ftrange;
-typedef int (*t_ftcompar_func)(const void*, const void*);
+struct s_merge_sorted_arrays
+{
+ void *base;
+ void *left;
+ void *right;
+};
+
+typedef int (*t_ftcompar_func)(const void*, const void*);
-t_bool ft_is_set(void *base, size_t nel, size_t width,
+t_ftbool ft_is_set(void *base, size_t nel, size_t width,
t_ftcompar_func compar);
-void ft_qsort(void *base, size_t nel, size_t width,
+int ft_compar_int(const void *a, const void *b);
+void ft_qsort(void *base, size_t nel, size_t width,
t_ftcompar_func compar);
-int ft_compar_int(const void *a, const void *b);
+int ft_mergesort(void *base, size_t nel, size_t width,
+ int (*compar)(const void *, const void *));
+int ft_heapsort(void *base, size_t nel, size_t width,
+ int (*compar)(const void *, const void *));
#endif
diff --git a/include/libft_mem.h b/include/libft_mem.h
index 5465d72..af3f4b5 100644
--- a/include/libft_mem.h
+++ b/include/libft_mem.h
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/31 10:35:57 by cacharle #+# #+# */
-/* Updated: 2020/01/31 10:35:59 by cacharle ### ########.fr */
+/* Updated: 2020/02/10 02:55:38 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
@@ -21,6 +21,7 @@ void *ft_memmove(void *dst, const void *src, size_t len);
void *ft_memchr(const void *s, int c, size_t n);
int ft_memcmp(const void *s1, const void *s2, size_t n);
void *ft_calloc(size_t count, size_t size);
+void ft_memswap(void *a, void *b, size_t size);
/*
** bloat ?
diff --git a/src/algo/ft_heapsort.c b/src/algo/ft_heapsort.c
new file mode 100644
index 0000000..afd395d
--- /dev/null
+++ b/src/algo/ft_heapsort.c
@@ -0,0 +1,50 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_heapsort.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/02/10 02:59:22 by cacharle #+# #+# */
+/* Updated: 2020/02/10 03:57:50 by cacharle ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft_algo.h"
+
+/* static void st_build_max_heap(void *base, size_t nel, size_t width, */
+/* int (*compar)(const void *, const void *)) */
+/* { */
+/* int i; */
+/* */
+/* i = 1; */
+/* while (i < nel) */
+/* { */
+/* compar(base + i * width, base + 2 * i * width) */
+/* */
+/* i++; */
+/* } */
+/* } */
+/* */
+/* static void st_heapify(void *base, size_t nel, size_t width, */
+/* int (*compar)(const void *, const void *)) */
+/* { */
+/* */
+/* } */
+
+int ft_heapsort(void *base, size_t nel, size_t width,
+ int (*compar)(const void *, const void *))
+{
+ /* size_t i; */
+ /* */
+ /* if (nel < 2) */
+ /* return (0); */
+ /* st_build_max_heap(base, nel, width, compar); */
+ /* i = -1; */
+ /* while (++i < nel) */
+ /* { */
+ /* ft_memswap(base, base + (nel - i - 1) * width); */
+ /* st_heapify(base, nel - i - 1, width, compar); */
+ /* } */
+ return (0);
+}
diff --git a/src/algo/ft_is_set.c b/src/algo/ft_is_set.c
index 8e45b49..3e7ae31 100644
--- a/src/algo/ft_is_set.c
+++ b/src/algo/ft_is_set.c
@@ -6,13 +6,14 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/19 07:17:15 by cacharle #+# #+# */
-/* Updated: 2020/01/19 08:21:12 by cacharle ### ########.fr */
+/* Updated: 2020/02/10 02:51:41 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
#include "libft.h"
+#include "libft_algo.h"
-t_bool ft_is_set(void *base, size_t nel, size_t width,
+t_ftbool ft_is_set(void *base, size_t nel, size_t width,
t_ftcompar_func compar)
{
size_t i;
diff --git a/src/algo/ft_mergesort.c b/src/algo/ft_mergesort.c
new file mode 100644
index 0000000..5af248e
--- /dev/null
+++ b/src/algo/ft_mergesort.c
@@ -0,0 +1,65 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_mergesort.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/02/10 02:26:41 by cacharle #+# #+# */
+/* Updated: 2020/02/10 02:59:10 by cacharle ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft_algo.h"
+
+static int st_mergesort_error(void *left, void *right)
+{
+ free(left);
+ free(right);
+ return (-1);
+}
+
+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 li;
+ size_t ri;
+
+ li = 0;
+ ri = 0;
+ while (li < nel / 2 && ri < nel - nel / 2)
+ {
+ if (compar(arrays->left + li * width, arrays->right + ri * width) < 0)
+ ft_memcpy(arrays->base, arrays->left + li++ * width, width);
+ else
+ ft_memcpy(arrays->base, arrays->right + ri++ * width, width);
+ }
+ 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);
+}
+
+int ft_mergesort(void *base, size_t nel, size_t width,
+ int (*compar)(const void *, const void *))
+{
+ size_t mid;
+ struct s_merge_sorted_arrays arrays;
+
+ if (nel < 2)
+ return (0);
+ mid = nel / 2;
+ if ((arrays.left = malloc(mid * width)) == NULL)
+ return (-1);
+ 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);
+ 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);
+ return (0);
+}
diff --git a/src/algo/ft_qsort.c b/src/algo/ft_qsort.c
index 8c125a1..9bcfcdf 100644
--- a/src/algo/ft_qsort.c
+++ b/src/algo/ft_qsort.c
@@ -6,11 +6,11 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/19 07:25:51 by cacharle #+# #+# */
-/* Updated: 2020/01/19 08:28:32 by cacharle ### ########.fr */
+/* Updated: 2020/02/10 02:55:14 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
-#include "libft.h"
+#include "libft_algo.h"
static t_ftrange ft_range_new(int lo, int hi)
{
diff --git a/src/mem/ft_memswap.c b/src/mem/ft_memswap.c
index 4abaa83..8661fda 100644
--- a/src/mem/ft_memswap.c
+++ b/src/mem/ft_memswap.c
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/19 07:56:43 by cacharle #+# #+# */
-/* Updated: 2020/01/19 08:22:17 by cacharle ### ########.fr */
+/* Updated: 2020/02/10 02:55:52 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
@@ -14,12 +14,12 @@
void ft_memswap(void *a, void *b, size_t size)
{
- t_byte tmp;
- t_byte *cast_a;
- t_byte *cast_b;
+ t_ftbyte tmp;
+ t_ftbyte *cast_a;
+ t_ftbyte *cast_b;
- cast_a = (t_byte*)a;
- cast_b = (t_byte*)b;
+ cast_a = (t_ftbyte*)a;
+ cast_b = (t_ftbyte*)b;
while (size-- > 0)
{
tmp = cast_a[size];
generated by cgit (git 2.34.1) at 2026-05-16 05:05:23 +0000