push_swap/custom_algo.c at main · 0obito/push_swap · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   custom_algo.c                                      :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: aelmsafe <aelmsafe@student.1337.ma>        +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2025/03/04 04:04:19 by aelmsafe          #+#    #+#             */
/*   Updated: 2025/03/06 02:04:18 by aelmsafe         ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include "push_swap.h"

size_t	ft_sqrt(size_t len)
{
	size_t	result;

	if (len == 0 || len == 1)
		return (len);
	result = 1;
	while (result * result < len)
		result++;
	return (result);
}

int	rotation_count(t_dlist_t *stack, int idx)
{
	int	c;

	c = 0;
	while (stack && stack->idx != idx)
	{
		stack = stack->next;
		c++;
	}
	if (!stack)
		return (-1);
	return (c);
}

void	sort_to_b(t_dlist_t **a, t_dlist_t **b)
{
	int	i;
	int	rot;
	int	range;

	i = 0;
	rot = 0;
	range = (int)ft_sqrt((size_t)stack_len(*a)) * 2;
	while (*a)
	{
		if ((*a)->idx <= i)
		{
			check_rr(a, b, &rot, 0);
			push(a, b, 'b');
			rot = 1;
			i++;
		}
		else if ((*a)->idx <= range + i)
		{
			check_rr(a, b, &rot, 0);
			push(a, b, 'b');
			i++;
		}
		else
			check_rr(a, b, &rot, 1);
	}
}

void	sort_to_a(t_dlist_t **a, t_dlist_t **b)
{
	int	len;
	int	r_count;

	len = stack_len(*b);
	while (len >= 1)
	{
		r_count = rotation_count(*b, len - 1);
		if (r_count <= stack_len(*b) / 2)
			while ((*b)->idx != len - 1)
				rotate(b, 'b');
		else
			while ((*b)->idx != len - 1)
				reverse_rotate(b, 'b');
		push(b, a, 'a');
		len--;
	}
}

void	my_sorting_algo(t_dlist_t **a, t_dlist_t **b)
{
	index_nodes(*a);
	sort_to_b(a, b);
	sort_to_a(a, b);
}