Push-Swap/sort_big.c at main · CBOcoding/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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   sort_big.c                                         :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: cborrome <cborrome@student.hive.fi>        +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2025/02/14 12:15:19 by cborrome          #+#    #+#             */
/*   Updated: 2025/02/17 12:36:26 by cborrome         ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include "push_swap.h"

int		find_target_position(int *stack_a, int size_a, int number);
void	calculate_cost(t_data *data, t_move *move);
void	execute_cheapest_move(t_data *data, t_move *moves);

void	sort_big(t_data *data)
{
	t_move	*move;
	int		smallest_index;

	allocate_stack_b(data);
	move = (t_move *)malloc((data->size_a + data->size_b) * sizeof(t_move));
	if (!move)
		error_free_exit(data);
	while (data->size_a > 3)
		push_to_b(data);
	sort_3(data, 'n');
	while (data->size_b > 0)
	{
		calculate_cost(data, move);
		execute_cheapest_move(data, move);
	}
	smallest_index = find_smallest_index(data->stack_a, data->size_a);
	if (smallest_index < data->size_a / 2)
		while (smallest_index-- > 0)
			rotate(data->stack_a, data->size_a, 'a');
	else
		while (smallest_index++ < data->size_a)
			reverse_rotate(data->stack_a, data->size_a, 'a');
	free(move);
	success_free_exit(data);
}

void	calculate_cost(t_data *data, t_move *move)
{
	int	i;

	i = 0;
	while (i < data->size_b)
	{
		if (i >= data->size_b)
			break ;
		move[i].index = i;
		move[i].target_index = find_target_position(data->stack_a, \
			data->size_a, data->stack_b[i]);
		if (move[i].target_index < data->size_a / 2)
			move[i].moves_a = move[i].target_index;
		else
			move[i].moves_a = data->size_a - move[i].target_index;
		if (data->size_b == 1)
			move[i].moves_b = 0;
		else if (i < data->size_b / 2)
			move[i].moves_b = i;
		else
			move[i].moves_b = data->size_b - i;
		move[i].cost = move[i].moves_a + move[i].moves_b + 1;
		i++;
	}
}

int	find_small_index(int *stack_a, int size_a)
{
	int	i;
	int	smallest_index;

	smallest_index = 0;
	i = 1;
	while (i < size_a)
	{
		if (stack_a[i] < stack_a[smallest_index])
			smallest_index = i;
		i++;
	}
	return (smallest_index);
}

int	find_large_index(int *stack_a, int size_a)
{
	int	i;
	int	largest_index;

	largest_index = 0;
	i = 1;
	while (i < size_a)
	{
		if (stack_a[i] > stack_a[largest_index])
			largest_index = i;
		i++;
	}
	return (largest_index);
}

int	find_target_position(int *stack_a, int size_a, int number)
{
	int	i;
	int	target_index;
	int	smallest_index;
	int	largest_index;

	target_index = 0;
	smallest_index = 0;
	i = 1;
	smallest_index = find_small_index(stack_a, size_a);
	if (number < stack_a[smallest_index])
		return (smallest_index);
	largest_index = find_large_index(stack_a, size_a);
	if (number > stack_a[largest_index])
		return ((largest_index + 1) % size_a);
	i = 1;
	while (i < size_a)
	{
		if (stack_a[i] > number && stack_a[i - 1] < number)
		{
			target_index = i;
			break ;
		}
		i++;
	}
	return (target_index);
}