WIP: better algo with 'sorting frame'

1 files changed, 89 insertions, 31 deletions

diff --git a/src/push_swap/sort.c b/src/push_swap/sort.c
index e1e738e..2e5c7fb 100644
--- a/src/push_swap/sort.c
+++ b/src/push_swap/sort.c
@@ -6,56 +6,114 @@
 /*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2020/01/19 09:12:02 by cacharle          #+#    #+#             */
-/*   Updated: 2020/01/19 13:45:37 by cacharle         ###   ########.fr       */
+/*   Updated: 2020/01/21 11:07:48 by cacharle         ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
 #include "push_swap.h"
 
-/*
- * pivot == stack top
- * push pivot to B
- * iterate over current partition and push < pivot onto B
- * 
- * 
- *
- */
-
 void	stack_print(t_stack *stack)
 {
-	printf("> ");
+	printf("%s> ", stack->tag == STACK_A ? "A" : "B");
 	for (int i = 0; i <= stack->top; i++)
 		printf("%2d | ", stack->elements[i]);
 	printf("\n");
 }
 
-void	push_swap_qsort(t_stack *main, t_stack *tmp)
+
+static int frame_length(t_stack *st, int frame_index)
+{
+	return stack_length(st) - frame_index;
+}
+
+/*
+** main       : stack to sort
+** tmp        : temporary stack used to store pivot > values
+** main_frame : main current sorting frame index
+**              (ignore values beyond a certain index,
+**               which bellong to previous recursions)
+**
+** store pivot value
+** hide it at the bottom of the stack
+** iterate over the current frame
+** if < pivot, push it to tmp stack
+** else, hide it with the pivot
+** put all hidden elements on the top of the stack
+** these form the new frame
+**
+** we have splitted the elements of the frame in upper and lower partition
+** 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)
 {
-	int pivot;
+	int	pivot;
+	int hidden_count;
+	int	frame_len;
+
+	pivot = stack_peek(main);
+	stack_rotate_print(main);
+	hidden_count = 1;
+	frame_len = frame_length(main, main_frame) - 1;
+	while (frame_len > 0)
+	{
+		if (stack_peek(main) < pivot)
+			stack_push_to_print(main, tmp);
+		else
+		{
+			stack_rotate_print(main);
+			hidden_count++;
+		}
+		frame_len--;
+	}
+	while (hidden_count-- > 0)
+		stack_reverse_rotate_print(main);
+}
 
-	if (stack_length(main) < 2)            // if empty or one element, sorted
+/*
+** main       : final stack where all sorted values will be stored
+** tmp        : temporary stack use to during partitionning
+** main_frame : main stack sorting frame
+** tmp_frame  : tmp stack sorting frame
+**
+** base condition : the current main frame contain 0 or 1 element
+** sort current partition and get new main frame
+** according to the new frame:
+**     sort the new partition
+**     sort the tmp stack
+** 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)
+{
+	if (frame_length(main, main_frame) < 2)
 		return ;
-	if (stack_length(main) == 2)           // if 2 elements and wrong order, swap then sorted
+	if (frame_length(main, main_frame) == 2)
 	{
-		if (stack_peek(main) > main->elements[0])
-			stack_swap_print(main);
+		if (stack_peek(main) > main->elements[stack_length(main) - 1])
+			stack_swap(main);
 		return ;
 	}
 
-	pivot = stack_peek(main);               // get pivot
-	stack_rotate_print(main);               // hide pivot
-	while (stack_peek(main) != pivot)       // iterate over every element that was bellow pivot in the stack
+	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));
+
+	int tmp_frame_len = frame_length(tmp, tmp_frame);
+	while (tmp_frame_len != 0)
 	{
-		if (stack_peek(main) < pivot)       // if lower than pivot, place it on tmp
-			stack_push_to_print(main, tmp);
-		else                                // else pass it
-			stack_rotate_print(main);
-	}
-	                                        // main contain all > pivot and the pivot hiself,
-									        // tmp  contain all < pivot
-	push_swap_qsort(tmp, main);             // sort the sub stack tmp
-	stack_push_to_print(main, tmp);         // pass the pivot to tmp which is already sorted to sort sub stack main
-	push_swap_qsort(main, tmp);             // sort main sub stack
-	while (!stack_empty(tmp))               // push all tmp stack on stack main
+		/* stack_reverse_rotate_print(tmp); */
 		stack_push_to_print(tmp, main);
+		tmp_frame_len--;
+	}
+}
+
+/*
+** wrapper for push_swap_qsort_rec
+*/
+
+void		push_swap_qsort(t_stack *a, t_stack *b)
+{
+	push_swap_qsort_rec(a, b, 0, 0);
 }