diff options
Diffstat (limited to 'src/push_swap')
| -rw-r--r-- | src/push_swap/main.c | 45 | ||||
| -rw-r--r-- | src/push_swap/push_swap.h | 29 | ||||
| -rw-r--r-- | src/push_swap/sort.c | 61 | ||||
| -rw-r--r-- | src/push_swap/stack_wrapper.c | 40 |
4 files changed, 175 insertions, 0 deletions
diff --git a/src/push_swap/main.c b/src/push_swap/main.c index 5019e79..b97feb3 100644 --- a/src/push_swap/main.c +++ b/src/push_swap/main.c @@ -1,4 +1,49 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* main.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/01/19 09:09:59 by cacharle #+# #+# */ +/* Updated: 2020/01/19 13:37:26 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "push_swap.h" + int main(int argc, char **argv) { + t_stack *a; + t_stack *b; + + if (argc == 1) + return (0); + if ((a = stack_new(argc - 1)) == NULL) + return (1); + if (parse(argc, argv, a) != STATUS_SUCCESS) + return (1); + if ((b = stack_new(stack_length(a))) == NULL) + { + 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; } diff --git a/src/push_swap/push_swap.h b/src/push_swap/push_swap.h index 0e553e0..e22fa9a 100644 --- a/src/push_swap/push_swap.h +++ b/src/push_swap/push_swap.h @@ -1,4 +1,33 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* push_swap.h :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/01/19 09:10:11 by cacharle #+# #+# */ +/* Updated: 2020/01/19 13:16:06 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + #ifndef PUSH_SWAP_H # define PUSH_SWAP_H +# include "libft.h" +# include "common.h" + +/* +** sort.c +*/ + +void push_swap_sort(t_stack *main, t_stack *tmp); + +/* +** stack_wrapper.c +*/ + +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); + #endif diff --git a/src/push_swap/sort.c b/src/push_swap/sort.c new file mode 100644 index 0000000..e1e738e --- /dev/null +++ b/src/push_swap/sort.c @@ -0,0 +1,61 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* sort.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/01/19 09:12:02 by cacharle #+# #+# */ +/* Updated: 2020/01/19 13:45:37 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("> "); + 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) +{ + int pivot; + + if (stack_length(main) < 2) // if empty or one element, sorted + return ; + if (stack_length(main) == 2) // if 2 elements and wrong order, swap then sorted + { + if (stack_peek(main) > main->elements[0]) + stack_swap_print(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 + { + 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_push_to_print(tmp, main); +} diff --git a/src/push_swap/stack_wrapper.c b/src/push_swap/stack_wrapper.c new file mode 100644 index 0000000..df44e23 --- /dev/null +++ b/src/push_swap/stack_wrapper.c @@ -0,0 +1,40 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* stack_wrapper.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/01/19 13:05:58 by cacharle #+# #+# */ +/* Updated: 2020/01/19 13:17:18 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "push_swap.h" + +void stack_swap_print(t_stack *stack) +{ + if (stack->tag == STACK_A) + ft_putendl("sa"); + if (stack->tag == STACK_B) + ft_putendl("sb"); + stack_swap(stack); +} + +void stack_rotate_print(t_stack *stack) +{ + if (stack->tag == STACK_A) + ft_putendl("ra"); + if (stack->tag == STACK_B) + ft_putendl("rb"); + stack_rotate(stack); +} + +void stack_push_to_print(t_stack *from, t_stack *to) +{ + if (to->tag == STACK_A) + ft_putendl("pa"); + if (to->tag == STACK_B) + ft_putendl("pb"); + stack_push_to(from, to); +} |