-
Notifications
You must be signed in to change notification settings - Fork 0
/
ft_sort_stack.c
196 lines (186 loc) · 7.43 KB
/
ft_sort_stack.c
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* ft_sort_stack.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: passunca <passunca@student.42porto.com> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2024/04/13 08:36:28 by passunca #+# #+# */
/* Updated: 2024/04/18 09:09:47 by passunca ### ########.fr */
/* */
/* ************************************************************************** */
#include "push_swap.h"
static void ft_exec_move(t_elem *stack_b, t_elem *stack_a,
int idx, int stack_len);
static int ft_best_op_idx(t_elem *stack_a, t_elem *stack_b, int stack_len);
static int ft_get_align_ops(t_elem *stack_a, t_elem *stack_b, int idx);
/* ft_sort_stack():
* - Initialize i to the start of the stack;
* - Initialize median to the median value of the stack;
* - Loop through the stack_a pushing elements to stack_b until there are only
* three elements left in stack_a;
* - If the current element in stack_b is greater than the median AND
* the number of elements in stack_a is greater than 3,
* rotate stack_b;
* - Increment i;
* - Sort the three elements in stack_a;
* - Reset i to the start of the stack_a;
* - Loop through the stack_b:
* - Calculate the best move for the current element in stack_b;
* - Increment i;
* - Rotate stack_a until the smallest number greater than the value at
* the top of stack_b is at the top of stack_a;
* - Pushes the top of stack_b to stack_a;
* - Rotate stack_a until its smallest element is at the top;
* */
void ft_sort_stack(t_elem *stack_a, t_elem *stack_b, int stack_len)
{
int i;
int median;
i = ft_stack_start(stack_a);
median = ft_get_median(stack_a);
while (i < (stack_len - 4))
{
ft_push_elem(stack_a, stack_b, "pb\n");
if ((stack_b[ft_stack_start(stack_b)].num > median)
&& ((ft_stack_end(stack_a) - ft_stack_start(stack_a)) + 1) > 3)
ft_rotate(stack_b, "rb\n");
++i;
}
ft_sort_three(stack_a);
i = ft_stack_start(stack_b);
while (i < ft_stack_end(stack_b))
{
ft_exec_move(stack_b, stack_a, \
ft_best_op_idx(stack_b, stack_a, stack_len), stack_len);
++i;
}
ft_rotate_top(stack_a, ft_min_above_thresh(stack_a, stack_b[i].num).index, \
"ra\n", "rra\n");
ft_push_elem(stack_b, stack_a, "pa\n");
ft_rotate_top(stack_a, ft_stack_min(stack_a).index, "ra\n", "rra\n");
}
/* ft_exec_move():
* - Get the start of the stack_a;
* - Get number of elements in stack_a & stack_b that are in the right order
* relative to eachother;
* - Moves the ordered elements from stack_b to stack_a;
* - If ordered elements were found, their indexes are adjusted accordingly;
* - Checks if the index is near the end if the stack or before the start
* of the stack, adjusting indexes if necessary;
* - Rotates stack_a so that the element at idx is at the top;
* - Again, checks if the index is near the end of the stack or before the
* start of the stack, adjusting indexes if necessary;
* - Checks if the smallest element in stack_b is greater than the top of
* stack_a OR if the largest element in stack_b is less than the top of
* stack_a;
* - If either conditions is true, rotates the stack_b so that it's
* smallest element is at the top,
* - Else, rotates stack_b so that it's smallest element greater than the top
* of stack_a is at the top;
* - Pushes the element in the top of stack_b to stack_a;
* */
static void ft_exec_move(t_elem *stack_b, t_elem *stack_a,
int idx, int stack_len)
{
int start;
int ordered;
start = ft_stack_start(stack_b);
ordered = ft_check_order(stack_b, stack_a, idx);
ft_order(stack_b, stack_a, idx);
if (ordered != 0)
idx -= ordered;
if (idx >= (stack_len - 2))
idx = (start + (idx - (stack_len - 1)));
else if (idx < start)
idx = (ft_stack_end(stack_b) + idx);
idx -= ft_rotate_top(stack_b, idx, "rb\n", "rrb\n");
if (idx >= (stack_len - 2))
idx = (start + (idx - (stack_len - 1)));
if ((ft_stack_min(stack_a).num > stack_b[idx].num)
|| (ft_stack_max(stack_a, -1).num < stack_b[idx].num))
ft_rotate_top(stack_a, ft_stack_min(stack_a).index, "ra\n", "rra\n");
else
ft_rotate_top(stack_a, \
ft_min_above_thresh(stack_a, stack_b[idx].num).index, "ra\n", "rra\n");
ft_push_elem(stack_b, stack_a, "pa\n");
}
/* ft_best_op_idx():
* ## Find the index of the element in stack_a that requires the least number
* of operations to be moved to the top of the stack and aligned with a
* corresponding element in stack_b.
*
* - Get the start of the stack_a;
* - Initialize idx to the start of the stack;
* - Initialize min_ops to -1 to keep track of the smallest cost;
* - Loop from idx till (stack_len - 1):
* - Calculate the cost of moving the element at idx of stack_a to the top
* and align it with the corresponding element at in stack_b;
* - If the cost is less than the current min_ops,
* - update min_ops;
* - Increment idx;
* - Return the index of the best move;
* */
static int ft_best_op_idx(t_elem *stack_a, t_elem *stack_b, int stack_len)
{
int idx;
int cost;
t_elem min_ops;
idx = ft_stack_start(stack_a);
min_ops.num = -1;
while (idx < (stack_len - 1))
{
cost = ft_get_align_ops(stack_a, stack_b, idx);
if ((cost < min_ops.num) || (min_ops.num == -1))
{
min_ops.num = cost;
min_ops.index = idx;
}
++idx;
}
return (min_ops.index);
}
/* ft_get_align_ops():
* ## Calculate the total number of operations needed to move an element at a
* given index in stack_a to the top, and to align a corresponding element in
* stack_b with it.
*
* - Initialize n_ops to 0 to keep count of the number of operations;
* - Calculate the cost of moving the element at idx of stack_a to the top
* and add it to n_ops;
* - Check if the smallest element in stack_b is greater than the element at
* idx in stack_a OR if the largest element in stack_b is less than the
* element at idx in stack_a;
* - Calculate the number of operations needed to move the smallest element
* in stack_b to the top, and adds this number to n_ops.
* - Else
* - Calculate the index of the smallest element in stack_b greater than
* the element at idx in stack_a;;
* - Calculate the number of operations needed to move the current element
* in stack_b to the top, and adds this number to n_ops;
* - Calculate the number of operations needed to align the two stacks;
* - If order is negative we take its absolute value;
* - Subtract order from n_ops to get the total number of operations;
* - Return (n_ops + 1);
* */
static int ft_get_align_ops(t_elem *stack_a, t_elem *stack_b, int idx)
{
int n_ops;
int order;
t_elem min_n_behind;
n_ops = 0;
n_ops += ft_getontop_ops(stack_a, idx, 0);
if ((ft_stack_min(stack_b).num > stack_a[idx].num) \
|| (ft_stack_max(stack_b, -1).num < stack_a[idx].num))
n_ops += ft_getontop_ops(stack_b, ft_stack_min(stack_b).index, 0);
else
{
min_n_behind = ft_min_above_thresh(stack_b, stack_a[idx].num);
n_ops += ft_getontop_ops(stack_b, stack_b[min_n_behind.index].index, 0);
}
order = ft_check_order(stack_a, stack_b, idx);
if (order < 0)
order = -order;
n_ops = (n_ops - order);
return (n_ops + 1);
}