First commitHEADmain

1 files changed, 115 insertions, 0 deletions

diff --git a/src/sort.c b/src/sort.c
new file mode 100644
index 0000000..ba3b755
--- /dev/null
+++ b/src/sort.c
@@ -0,0 +1,115 @@
+/*
+sort_stack Copyright (C) 2026 yctct
+
+This program is free software: you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation, either version 3 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program.  If not, see <https://www.gnu.org/licenses/>.
+*/
+
+
+#include "../include/push_swap.h"
+
+int	greatest_smallest_value(int element, t_list *stack)
+{
+	int	saved;
+
+	saved = (ft_lstmin(stack))->value;
+	while (stack)
+	{
+		if (stack->value <= element && stack->value > saved)
+			saved = stack->value;
+		stack = stack->next;
+	}
+	return (saved);
+}
+
+int	find_position_stack(int element, t_list *stack)
+{
+	int	position;
+
+	position = ft_lstmax(stack)->index;
+	while (stack)
+	{
+		if (element >= stack->value
+			&& stack->value >= greatest_smallest_value(element, stack))
+		{
+			position = stack->index;
+			return (position);
+		}
+		stack = stack->next;
+	}
+	return (position);
+}
+
+int	find_cheapest_element(t_list *src, t_list *dst)
+{
+	int	index;
+	int	cost;
+	int	node_cost;
+
+	cost = 0;
+	index = src->index;
+	while (src)
+	{
+		node_cost = src->index;
+		node_cost += find_position_stack(src->value, dst);
+		if (!cost)
+			cost = node_cost;
+		else if (cost && (node_cost < cost))
+		{
+			cost = node_cost;
+			index = src->index;
+		}
+		src = src->next;
+	}
+	return (index);
+}
+
+void	push_and_sort(t_list **src, t_list **dst)
+{
+	int		position_a;
+	int		position_b;
+	t_list	*cheapst_element;
+
+	while (*src)
+	{
+		position_a = find_cheapest_element(*src, *dst);
+		cheapst_element = *src;
+		while (cheapst_element->index < position_a)
+			cheapst_element = cheapst_element->next;
+		position_b = find_position_stack(cheapst_element->value, *dst);
+		rotate_stacks(position_a, position_b, src, dst);
+		pb(src, dst);
+	}
+}
+
+void	sort(t_list **src)
+{
+	t_list	*dst;
+
+	dst = NULL;
+	pb(src, &dst);
+	pb(src, &dst);
+	push_and_sort(src, &dst);
+	while (dst)
+		pa(&dst, src);
+	if ((ft_lstmin(*src))->index < (ft_lstsize(*src) / 2))
+	{
+		while ((*src)->value != ft_lstmin(*src)->value)
+			ra(src);
+	}
+	else
+	{
+		while ((*src)->value != ft_lstmin(*src)->value)
+			rra(src);
+	}
+}