Added micro optimisation when sorting frame == 2 and less reverse rotate when frame == full stack, norming

4 files changed, 29 insertions, 41 deletions

diff --git a/src/push_swap/main.c b/src/push_swap/main.c
index b97feb3..fa34b35 100644
--- a/src/push_swap/main.c
+++ b/src/push_swap/main.c
@@ -6,13 +6,13 @@
 /*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2020/01/19 09:09:59 by cacharle          #+#    #+#             */
-/*   Updated: 2020/01/19 13:37:26 by cacharle         ###   ########.fr       */
+/*   Updated: 2020/01/22 10:36:31 by cacharle         ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
 #include "push_swap.h"
 
-int main(int argc, char **argv)
+int	main(int argc, char **argv)
 {
 	t_stack	*a;
 	t_stack	*b;
@@ -28,22 +28,10 @@ int main(int argc, char **argv)
 		stack_destroy(a);
 		return (1);
 	}
-
 	a->tag = STACK_A;
 	b->tag = STACK_B;
-
 	push_swap_qsort(a, b);
-	/* push_swap_qsort(a, b); */
-	/* push_swap_qsort(a, b); */
-	/* push_swap_qsort(a, b); */
-	/* push_swap_qsort(a, b); */
-
-	/* printf("\na: "); */
-	/* stack_print(a); */
-	/* printf("b: "); */
-	/* stack_print(b); */
-
 	stack_destroy(a);
 	stack_destroy(b);
-	return 0;
+	return (0);
 }
diff --git a/src/push_swap/push_swap.h b/src/push_swap/push_swap.h
index 0bffca5..87443a1 100644
--- a/src/push_swap/push_swap.h
+++ b/src/push_swap/push_swap.h
@@ -6,7 +6,7 @@
 /*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2020/01/19 09:10:11 by cacharle          #+#    #+#             */
-/*   Updated: 2020/01/22 08:59:59 by cacharle         ###   ########.fr       */
+/*   Updated: 2020/01/22 10:42:44 by cacharle         ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
@@ -20,7 +20,7 @@
 ** sort.c
 */
 
-void	push_swap_sort(t_stack *main, t_stack *tmp);
+void	push_swap_qsort(t_stack *main, t_stack *tmp);
 
 /*
 ** stack_wrapper.c
diff --git a/src/push_swap/sort.c b/src/push_swap/sort.c
index c712d50..1639769 100644
--- a/src/push_swap/sort.c
+++ b/src/push_swap/sort.c
@@ -6,24 +6,15 @@
 /*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2020/01/19 09:12:02 by cacharle          #+#    #+#             */
-/*   Updated: 2020/01/22 08:55:55 by cacharle         ###   ########.fr       */
+/*   Updated: 2020/01/22 11:08:00 by cacharle         ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
 #include "push_swap.h"
 
-void	stack_print(t_stack *stack)
+static int	frame_length(t_stack *st, int frame_index)
 {
-	printf("%s> ", stack->tag == STACK_A ? "A" : "B");
-	for (int i = 0; i <= stack->top; i++)
-		printf("%2d | ", stack->elements[i]);
-	printf("\n");
-}
-
-
-static int frame_length(t_stack *st, int frame_index)
-{
-	return stack_length(st) - frame_index;
+	return (stack_length(st) - frame_index);
 }
 
 /*
@@ -45,7 +36,8 @@ static int frame_length(t_stack *st, int frame_index)
 ** each of those will be sorted in the next recursion
 */
 
-static void	push_swap_qsort_partition(t_stack *main, t_stack *tmp, int main_frame)
+static void	push_swap_qsort_partition(t_stack *main, t_stack *tmp,
+										int main_frame)
 {
 	int	pivot;
 	int hidden_count;
@@ -57,7 +49,8 @@ static void	push_swap_qsort_partition(t_stack *main, t_stack *tmp, int main_fram
 	frame_len = frame_length(main, main_frame) - 1;
 	while (frame_len > 0)
 	{
-		if (main->tag == STACK_A ? (stack_peek(main) < pivot) : (stack_peek(main) > pivot))
+		if (main->tag == STACK_A ?
+				(stack_peek(main) < pivot) : (stack_peek(main) > pivot))
 			stack_push_to_print(main, tmp);
 		else
 		{
@@ -66,6 +59,8 @@ static void	push_swap_qsort_partition(t_stack *main, t_stack *tmp, int main_fram
 		}
 		frame_len--;
 	}
+	if (stack_peek(main) == pivot)
+		return ;
 	while (hidden_count-- > 0)
 		stack_reverse_rotate_print(main);
 }
@@ -84,24 +79,29 @@ static void	push_swap_qsort_partition(t_stack *main, t_stack *tmp, int main_fram
 ** push all elements of tmp on main
 */
 
-static void	push_swap_qsort_rec(t_stack *main, t_stack *tmp, int main_frame, int tmp_frame)
+static void	push_swap_qsort_rec(t_stack *main, t_stack *tmp,
+								int main_frame, int tmp_frame)
 {
+	int	tmp_frame_len;
+
 	if (frame_length(main, main_frame) < 2)
 		return ;
-
+	if (frame_length(main, main_frame) == 2)
+	{
+		if (main->tag == STACK_A ?
+				main->elements[main->top] > main->elements[main->top - 1]
+				: main->elements[main->top] < main->elements[main->top - 1])
+			stack_swap_print(main);
+		return ;
+	}
 	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);
 	push_swap_qsort_rec(main, tmp, main_frame, stack_length(tmp));
 	stack_push_to_print(tmp, main);
-
-	int tmp_frame_len = frame_length(tmp, tmp_frame);
-	while (tmp_frame_len != 0)
-	{
+	tmp_frame_len = frame_length(tmp, tmp_frame);
+	while (tmp_frame_len-- > 0)
 		stack_push_to_print(tmp, main);
-		tmp_frame_len--;
-	}
 }
 
 /*
diff --git a/src/push_swap/stack_wrapper.c b/src/push_swap/stack_wrapper.c
index 798f174..be18c0e 100644
--- a/src/push_swap/stack_wrapper.c
+++ b/src/push_swap/stack_wrapper.c
@@ -6,7 +6,7 @@
 /*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2020/01/19 13:05:58 by cacharle          #+#    #+#             */
-/*   Updated: 2020/01/21 10:19:58 by cacharle         ###   ########.fr       */
+/*   Updated: 2020/01/22 10:04:44 by cacharle         ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */