aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/checker/check.c30
-rw-r--r--src/checker/checker.h3
-rw-r--r--src/checker/main.c2
-rw-r--r--src/common/common.h2
-rw-r--r--src/push_swap/sort.c104
5 files changed, 80 insertions, 61 deletions
diff --git a/src/checker/check.c b/src/checker/check.c
index 1459dc6..40550b5 100644
--- a/src/checker/check.c
+++ b/src/checker/check.c
@@ -6,12 +6,25 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/18 10:16:08 by cacharle #+# #+# */
-/* Updated: 2021/09/10 10:26:47 by charles ### ########.fr */
+/* Updated: 2021/09/10 15:36:14 by charles ### ########.fr */
/* */
/* ************************************************************************** */
#include "checker.h"
+static t_bool stack_sorted(t_stack *stack)
+{
+ int i;
+
+ if (stack_length(stack) < 2)
+ return (TRUE);
+ i = stack->top + 1;
+ while (--i > 0)
+ if (stack->elements[i] > stack->elements[i - 1])
+ return (FALSE);
+ return (TRUE);
+}
+
t_status check(t_stack *a, t_stack *b)
{
t_status read_status;
@@ -75,7 +88,7 @@ t_status exec_action(char action_id[ACTION_ID_BUF_SIZE],
int i;
i = 0;
- while (ft_strcmp(action_id, g_actions[i].id) != 0)
+ while (i < g_actions_size && ft_strcmp(action_id, g_actions[i].id) != 0)
i++;
if (i == g_actions_size)
return (STATUS_ERROR);
@@ -91,16 +104,3 @@ t_status exec_action(char action_id[ACTION_ID_BUF_SIZE],
return (STATUS_ERROR);
return (STATUS_SUCCESS);
}
-
-t_bool stack_sorted(t_stack *stack)
-{
- int i;
-
- if (stack_length(stack) < 2)
- return (TRUE);
- i = stack->top + 1;
- while (--i > 0)
- if (stack->elements[i] > stack->elements[i - 1])
- return (FALSE);
- return (TRUE);
-}
diff --git a/src/checker/checker.h b/src/checker/checker.h
index d049e21..638f43f 100644
--- a/src/checker/checker.h
+++ b/src/checker/checker.h
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/18 10:16:12 by cacharle #+# #+# */
-/* Updated: 2021/09/10 10:26:37 by charles ### ########.fr */
+/* Updated: 2021/09/10 12:04:41 by charles ### ########.fr */
/* */
/* ************************************************************************** */
@@ -45,6 +45,5 @@ t_status check(t_stack *a, t_stack *b);
t_status read_action(t_stack *a, t_stack *b);
t_status exec_action(char action_id[ACTION_ID_BUF_SIZE],
t_stack *a, t_stack *b);
-t_bool stack_sorted(t_stack *stack);
#endif
diff --git a/src/checker/main.c b/src/checker/main.c
index ca38105..394dddc 100644
--- a/src/checker/main.c
+++ b/src/checker/main.c
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/18 10:16:14 by cacharle #+# #+# */
-/* Updated: 2021/09/10 10:33:05 by charles ### ########.fr */
+/* Updated: 2021/09/10 12:08:44 by charles ### ########.fr */
/* */
/* ************************************************************************** */
diff --git a/src/common/common.h b/src/common/common.h
index c4efad8..d3cafc4 100644
--- a/src/common/common.h
+++ b/src/common/common.h
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/18 11:20:54 by cacharle #+# #+# */
-/* Updated: 2021/09/10 10:33:19 by charles ### ########.fr */
+/* Updated: 2021/09/10 12:12:04 by charles ### ########.fr */
/* */
/* ************************************************************************** */
diff --git a/src/push_swap/sort.c b/src/push_swap/sort.c
index 588dc54..b2d4838 100644
--- a/src/push_swap/sort.c
+++ b/src/push_swap/sort.c
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/19 09:12:02 by cacharle #+# #+# */
-/* Updated: 2021/09/10 10:48:01 by charles ### ########.fr */
+/* Updated: 2021/09/10 19:35:34 by charles ### ########.fr */
/* */
/* ************************************************************************** */
@@ -17,42 +17,48 @@ static int frame_length(t_stack *st, int frame_index)
return (stack_length(st) - frame_index);
}
-/* static void push_swap_sort3(t_stack *main, int main_frame) */
-/* { */
-/* #<{(| 1 < 2 < 3 |)}># */
-/* #<{(| 2 < 3 < 1 |)}># */
-/* #<{(| 3 < 1 < 2 |)}># */
-/* #<{(| 3 < 2 < 1 |)}># */
-/* #<{(| 2 < 1 < 3 |)}># */
-/* #<{(| 1 < 3 < 2 |)}># */
-/* */
-/* int a, b, c; */
-/* */
-/* a = main->elements[main->top]; */
-/* b = main->elements[main->top - 1]; */
-/* c = main->elements[main->top - 2]; */
-/* */
-/* if (a < b && b < c) */
-/* return ; */
-/* if (a < b && b > c) */
-/* stack_swap_print(main); */
-/* */
-/* if (a > b && b < c) */
-/* stack_swap_print(main); */
-/* if (a < b && b > c) */
-/* stack_swap_print(main); */
-/* if (a < b && b > c) */
-/* stack_swap_print(main); */
-/* if (a < b && b > c) */
-/* stack_swap_print(main); */
-/* } */
-
-static int not_a_ternary(bool cond, int x, int y)
+static void push_swap_sort3(t_stack *main)
{
- if (cond)
- return (x);
+ int a, b, c;
+
+ a = main->elements[main->top];
+ b = main->elements[main->top - 1];
+ c = main->elements[main->top - 2];
+
+ /* 2 3 1 rra */
+ if (a < b && b > c && a > c)
+ stack_reverse_rotate_print(main);
+
+ /* 3 1 2 ra */
+ else if (a > b && b < c && a > c)
+ stack_rotate_print(main);
+
+ /* 3 2 1 ra sa */
+ else if (a > b && b > c && a > c)
+ {
+ stack_rotate_print(main);
+ stack_swap_print(main);
+ }
+
+ /* 2 1 3 sa */
+ else if (a > b && b < c && a < c)
+ stack_swap_print(main);
+
+ /* 1 3 2 sa ra*/
+ else if (a < b && b > c && a < c)
+ {
+ stack_swap_print(main);
+ stack_rotate_print(main);
+ }
+}
+
+
+static int stack_cmp(t_stack *stack, int x, int y)
+{
+ if (stack->tag == STACK_A)
+ return (x < y);
else
- return (y);
+ return (x > y);
}
/*
@@ -87,8 +93,7 @@ static void push_swap_qsort_partition(t_stack *main, t_stack *tmp,
frame_len = frame_length(main, main_frame) - 1;
while (frame_len > 0)
{
- if (not_a_ternary(main->tag == STACK_A,
- stack_peek(main) < pivot, stack_peek(main) > pivot))
+ if (stack_cmp(main, stack_peek(main) , pivot))
stack_push_to_print(main, tmp);
else
{
@@ -103,6 +108,20 @@ static void push_swap_qsort_partition(t_stack *main, t_stack *tmp,
stack_reverse_rotate_print(main);
}
+static bool stack_frame_sorted(t_stack *stack, int frame_len)
+{
+ int i;
+
+ i = 0;
+ while (i < frame_len - 1)
+ {
+ if (stack_cmp(stack, stack->elements[stack->top - 1 - i], stack->elements[stack->top - i]))
+ return false;
+ i++;
+ }
+ return true;
+}
+
/*
** main : final stack where all sorted values will be stored
** tmp : temporary stack use to during partitionning
@@ -122,18 +141,19 @@ static void push_swap_qsort_rec(t_stack *main, t_stack *tmp,
{
int tmp_frame_len;
+ /* printf("f: %d\n", main_frame); */
if (frame_length(main, main_frame) < 2)
return ;
+ if (stack_frame_sorted(main, frame_length(main, main_frame)))
+ return ;
+ if (main->tag == STACK_A && stack_length(main) == 3)
+ return push_swap_sort3(main);
if (frame_length(main, main_frame) == 2)
{
- if (not_a_ternary(main->tag == STACK_A,
- main->elements[main->top] > main->elements[main->top - 1],
- main->elements[main->top] < main->elements[main->top - 1]))
+ if (stack_cmp(main, main->elements[main->top - 1], main->elements[main->top]))
stack_swap_print(main);
return ;
}
- /* if (frame_length(main main_frame) == 3) */
- /* return push_swap_sort3(main, main_frame); */
push_swap_qsort_partition(main, tmp, main_frame);
push_swap_qsort_rec(tmp, main, tmp_frame, stack_length(main));
stack_push_to_print(main, tmp);
generated by cgit (git 2.34.1) at 2026-05-16 09:45:23 +0000