From 0acdc4fec5cae4e619d0f4f8bd67e171bffa110e Mon Sep 17 00:00:00 2001 From: Charles Date: Mon, 10 Feb 2020 02:16:49 +0100 Subject: Added ft_lstsort, ft_lstsorted_merge --- src/lst/ft_lstsort.c | 40 ++++++++++++++++++++++++++++++++++++++++ src/lst/ft_lstsorted_merge.c | 36 ++++++++++++++++++++++++++++++++++++ 2 files changed, 76 insertions(+) create mode 100644 src/lst/ft_lstsort.c create mode 100644 src/lst/ft_lstsorted_merge.c (limited to 'src/lst') diff --git a/src/lst/ft_lstsort.c b/src/lst/ft_lstsort.c new file mode 100644 index 0000000..883604f --- /dev/null +++ b/src/lst/ft_lstsort.c @@ -0,0 +1,40 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_lstsort.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/02/10 01:53:55 by cacharle #+# #+# */ +/* Updated: 2020/02/10 02:09:28 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft_lst.h" + +void ft_lstsort(t_ftlst **begin_list, int (*cmp)(void *, void*)) +{ + t_ftlst *fast; + t_ftlst *slow; + t_ftlst *middle; + + if (begin_list == NULL || *begin_list == NULL + || (*begin_list)->next == NULL) + return ; + fast = (*begin_list)->next; + slow = *begin_list; + while (fast != NULL) + { + fast = fast->next; + if (fast != NULL) + { + fast = fast->next; + slow = slow->next; + } + } + middle = slow->next; + slow->next = NULL; + ft_lstsort(begin_list, cmp); + ft_lstsort(&middle, cmp); + *begin_list = ft_lstsorted_merge(*begin_list, middle, cmp); +} diff --git a/src/lst/ft_lstsorted_merge.c b/src/lst/ft_lstsorted_merge.c new file mode 100644 index 0000000..c3d0391 --- /dev/null +++ b/src/lst/ft_lstsorted_merge.c @@ -0,0 +1,36 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_lstsorted_merge.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/02/10 01:58:52 by cacharle #+# #+# */ +/* Updated: 2020/02/10 02:13:37 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft_lst.h" + +t_ftlst *ft_lstsorted_merge(t_ftlst *l1, t_ftlst *l2, + int (*cmp)(void *, void *)) +{ + t_ftlst *merged; + + merged = NULL; + if (l1 == NULL) + return (l2); + if (l2 == NULL) + return (l1); + if (cmp(l1->content, l2->content) < 0) + { + merged = l1; + merged->next = ft_lstsorted_merge(l1->next, l2, cmp); + } + else + { + merged = l2; + merged->next = ft_lstsorted_merge(l1, l2->next, cmp); + } + return (merged); +} -- cgit