diff options
| -rw-r--r-- | src/common/stack_helper.c | 12 | ||||
| -rw-r--r-- | src/push_swap/push_swap.h | 3 | ||||
| -rw-r--r-- | src/push_swap/sort.c | 120 | ||||
| -rw-r--r-- | src/push_swap/stack_wrapper.c | 11 | ||||
| -rwxr-xr-x | visualizer.rb | 36 |
5 files changed, 127 insertions, 55 deletions
diff --git a/src/common/stack_helper.c b/src/common/stack_helper.c index 6ea7cef..31d0fea 100644 --- a/src/common/stack_helper.c +++ b/src/common/stack_helper.c @@ -6,36 +6,36 @@ /* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2020/01/19 06:40:18 by cacharle #+# #+# */ -/* Updated: 2020/01/19 07:03:32 by cacharle ### ########.fr */ +/* Updated: 2020/01/21 11:08:06 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ #include "common.h" -void stack_swap_2(t_stack *stack_a, t_stack *stack_b) +inline void stack_swap_2(t_stack *stack_a, t_stack *stack_b) { stack_swap(stack_a); stack_swap(stack_b); } -void stack_rotate_2(t_stack *stack_a, t_stack *stack_b) +inline void stack_rotate_2(t_stack *stack_a, t_stack *stack_b) { stack_rotate(stack_a); stack_rotate(stack_b); } -void stack_reverse_rotate_2(t_stack *stack_a, t_stack *stack_b) +inline void stack_reverse_rotate_2(t_stack *stack_a, t_stack *stack_b) { stack_reverse_rotate(stack_a); stack_reverse_rotate(stack_b); } -t_bool stack_empty(t_stack *stack) +inline t_bool stack_empty(t_stack *stack) { return (stack->top == -1); } -int stack_length(t_stack *stack) +inline int stack_length(t_stack *stack) { return (stack->top + 1); } diff --git a/src/push_swap/push_swap.h b/src/push_swap/push_swap.h index e22fa9a..9426cca 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/19 13:16:06 by cacharle ### ########.fr */ +/* Updated: 2020/01/21 10:20:04 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ @@ -29,5 +29,6 @@ void push_swap_sort(t_stack *main, t_stack *tmp); void stack_swap_print(t_stack *stack); void stack_rotate_print(t_stack *stack); void stack_push_to_print(t_stack *from, t_stack *to); +void stack_reverse_rotate_print(t_stack *stack); #endif 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); } diff --git a/src/push_swap/stack_wrapper.c b/src/push_swap/stack_wrapper.c index df44e23..798f174 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/19 13:17:18 by cacharle ### ########.fr */ +/* Updated: 2020/01/21 10:19:58 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ @@ -38,3 +38,12 @@ void stack_push_to_print(t_stack *from, t_stack *to) ft_putendl("pb"); stack_push_to(from, to); } + +void stack_reverse_rotate_print(t_stack *stack) +{ + if (stack->tag == STACK_A) + ft_putendl("rra"); + if (stack->tag == STACK_B) + ft_putendl("rrb"); + stack_reverse_rotate(stack); +} diff --git a/visualizer.rb b/visualizer.rb index 343b46b..3a3a35d 100755 --- a/visualizer.rb +++ b/visualizer.rb @@ -51,40 +51,45 @@ def red(s) "\033[31m#{s}\033[0m" end -def print_stacks(a, b) +def print_stacks(a, b, max_elem) puts " A B\n" - puts "------------------------------" + puts "-" * (2 * max_elem + 10) - a_str = ARGV.length.times.map { |i| ARGV.length - i }.map do |i| + a_str = (1 + ARGV.length).times.map { |i| ARGV.length - i }.map do |i| unless a.elements[i].nil? - "| " + a.elements[i].to_s.ljust(2) + " " + green(("+" * a.elements[i]).ljust(10)) + "| " + "| " + a.elements[i].to_s.ljust(2) + " " + green(("+" * a.elements[i]).ljust(max_elem)) + "| " else - "| #{green(' ' * 10)}| " + "| #{green(' ' * max_elem)}| " end end - b_str = ARGV.length.times.map { |i| ARGV.length - i }.map do |i| + b_str = (1 + ARGV.length).times.map { |i| ARGV.length - i }.map do |i| unless b.elements[i].nil? - b.elements[i].to_s.ljust(2) + " " + red(("+" * b.elements[i]).ljust(10)) + "|" + b.elements[i].to_s.ljust(2) + " " + red(("+" * b.elements[i]).ljust(max_elem)) + "|" else - " #{red(' ' * 10)}|" + " #{red(' ' * max_elem)}|" end end puts a_str.zip(b_str).map { |ab| ab[0] + ab[1] }.join("\n") - puts "------------------------------" + puts "-" * (2 * max_elem + 10) puts end -a = Stack.new(ARGV.map(&:to_i)) +a = Stack.new(ARGV.map(&:to_i).reverse) b = Stack.new([]) +max_elem = a.elements.max + +puts a.elements.length + # lines = $stdin.read.split("\n") + +print_stacks(a, b, max_elem) + $stdin.each_line do |op| - print_stacks(a, b) op.strip! - puts "> #{op}" case op when "sa" then a.swap when "sb" then b.swap @@ -108,9 +113,8 @@ $stdin.each_line do |op| a.rotate_rev b.rotate_rev else - puts "Error: wrong op" - exit + puts "Debug:" end + puts "> #{op}" + print_stacks(a, b, max_elem) end - -print_stacks(a, b) |