1 files changed, 97 insertions, 0 deletions
diff --git a/libft/src/algo/ft_qsort.c b/libft/src/algo/ft_qsort.c
new file mode 100644
index 0000000..0c1c0f7
--- /dev/null
+++ b/libft/src/algo/ft_qsort.c
@@ -0,0 +1,97 @@
+/* ************************************************************************** */
+/*                                                                            */
+/*                                                        :::      ::::::::   */
+/*   ft_qsort.c                                         :+:      :+:    :+:   */
+/*                                                    +:+ +:+         +:+     */
+/*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
+/*                                                +#+#+#+#+#+   +#+           */
+/*   Created: 2020/01/19 07:25:51 by cacharle          #+#    #+#             */
+/*   Updated: 2020/04/04 22:10:29 by charles          ###   ########.fr       */
+/*                                                                            */
+/* ************************************************************************** */
+
+#include "libft_algo.h"
+
+/*
+** \brief    Helper to create a new range
+** \param lo  Lower bound
+** \param hi  Higher bound
+** \return    Range struct (not allocated)
+*/
+
+static t_ftrange	ft_range_new(int lo, int hi)
+{
+	t_ftrange range;
+
+	range.lo = lo;
+	range.hi = hi;
+	return (range);
+}
+
+/*
+** \brief         Array partitionning,
+**                takes a pivot and place every element lower than it before
+**                and every element greater after
+** \param base    Partitioned array
+** \param range   Lower and upper bound
+** \param width   Single element size
+** \param compar  Comparison function
+*/
+
+static int			ft_qsort_partition(void *base, t_ftrange range,
+										size_t width, t_ftcompar_func compar)
+{
+	void	*pivot;
+	int		p;
+	int		i;
+
+	pivot = base + (range.hi * width);
+	p = range.lo;
+	i = range.lo - 1;
+	while (++i < range.hi)
+	{
+		if (compar(base + (i * width), pivot) < 0)
+		{
+			ft_memswap(base + (i * width), base + (p * width), width);
+			p++;
+		}
+	}
+	ft_memswap(pivot, base + (p * width), width);
+	return (p);
+}
+
+/*
+** \brief         Qsort recursion function
+** \param base    Array to sort
+** \param range   Lower and upper bound which define the area to sort
+** \param width   Single element size
+** \param compar  Comparision function
+*/
+
+static void			ft_qsort_rec(void *base, t_ftrange range,
+										size_t width, t_ftcompar_func compar)
+{
+	int	pivot;
+
+	if (range.lo >= range.hi)
+		return ;
+	pivot = ft_qsort_partition(base, range, width, compar);
+	ft_qsort_rec(base, ft_range_new(range.lo, pivot - 1), width, compar);
+	ft_qsort_rec(base, ft_range_new(pivot + 1, range.hi), width, compar);
+}
+
+/*
+** \brief         Sort an array using the Quick sort algorithm
+** \param base    Array to sort
+** \param nel     Number of element in the array
+** \param width   Size of each element
+** \param compar  Comparision function
+*/
+
+void				ft_qsort(void *base, size_t nel, size_t width,
+								t_ftcompar_func compar)
+{
+	if (width == 0 || nel < 2)
+		return ;
+	ft_qsort_rec(base, ft_range_new(0, nel - 1), width, compar);
+}