From 9c7edcabd7a1bc2ac9362d009ea483a5fdb610e3 Mon Sep 17 00:00:00 2001 From: Lukas Jiriste Date: Fri, 23 Feb 2024 12:13:25 +0100 Subject: [PATCH] Weaken the 3 or less sort and fix binary search The a_sort_three_or_less function needs not to rotate, as the a stack will be rotated many times during the insertion. --- src/push.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 46 insertions(+), 6 deletions(-) diff --git a/src/push.c b/src/push.c index fcb1e93..e8893dc 100644 --- a/src/push.c +++ b/src/push.c @@ -6,7 +6,7 @@ /* By: ljiriste +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2024/01/24 13:17:32 by ljiriste #+# #+# */ -/* Updated: 2024/02/23 10:15:20 by ljiriste ### ########.fr */ +/* Updated: 2024/02/23 11:58:08 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ @@ -41,20 +41,38 @@ void a_sort_three_or_less(t_stacks *s) } if (steps_to_smaller == 2) print_swap(s, a); - if (max == stack_top(&s->a) && !is_sorted(&s->a)) - print_rotate(s, a); - else if (!is_sorted(&s->a)) - print_reverse_rotate(s, a); return ; } +size_t find_minind(t_stack *s) +{ + size_t minind; + size_t i; + int min; + + min = INT_MAX; + i = 0; + while (i < s->stack.size) + { + if (min > stack_top(s)) + { + minind = i; + min = stack_top(s); + } + stack_rotate(s, 1); + ++i; + } + return (minind); +} + size_t find_target_ind(t_stack *stack, int val) { size_t cur_step; const size_t initial_ind = stack->ind; size_t res; - cur_step = stack->stack.size / 2; + stack_rotate(stack, find_minind(stack)); + cur_step = stack->stack.size / 2 + 1; stack_rotate(stack, cur_step); while (cur_step > 1) { @@ -154,6 +172,27 @@ void get_push_indeces(t_stacks *s, int *ind_a, int *ind_b) return ; } +void rotate_a_to_sort(t_stacks *s) +{ + size_t minind; + t_action *print_action; + + minind = find_minind(&s->a); + if (minind < s->a.stack.size / 2) + print_action = print_rotate; + else + { + minind -= s->a.stack.size / 2; + print_action = print_reverse_rotate; + } + while (minind > 0) + { + print_action(s, a); + --minind; + } + return ; +} + void sort(t_stacks *s) { int ind_a; @@ -170,6 +209,7 @@ void sort(t_stacks *s) prepare_stacks(s, ind_a, ind_b); print_push(s, a); } + rotate_a_to_sort(s); return ; } -- 2.30.2