Added check for already sorted stack, Added special cases for length 3 stacks, Added test.sh benchmark and testing all permutations

1 files changed, 62 insertions, 42 deletions

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);