/Push_swap

This is another 42 exercise on sorting algorithms disguised as a game that will eat hours of your sleep 😴

Primary LanguageC

                                     d8
                                     88
          88d888b. dP    dP ,d888'   88d8888b.        ,d888'   dP  dP  dP .d8888b. 88d888b.
          88'  '88 88    88 Y8ooooo. 88'   `88        Y8ooooo. 88  88  88 88'  `88 88'  '88
          88.  .88 88.  .88       88 88     88              88 88.88b.88' 88.  .88 88.  .88
          8Y888P'  `888888' `88888P' 8P     dP d8888P `88888P' 8888P Y8P  `88888P8 8Y888P' 
          88                                                                       88
          8P                                                                       8P

Push_swap

School algorithm project push_swap: the aim is to sort data using only two stacks and a limited set of instructions.
Norminette codestyle.
subject.pdf


Sorting 100 numbers takes an average of 660 steps
Sorting 500 numbers takes an average of 4930 steps
Evaluation of the algorithm by subject: 5/5

Command

  • sa : swap a - swap the first 2 elements at the top of stack a. Do nothing if there is only one or no elements).
  • sb : swap b - swap the first 2 elements at the top of stack b. Do nothing if there is only one or no elements).
  • ss : sa and sb at the same time.
  • pa : push a - take the first element at the top of b and put it at the top of a. Do nothing if b is empty.
  • pb : push b - take the first element at the top of a and put it at the top of b. Do nothing if a is empty.
  • ra : rotate a - shift up all elements of stack a by 1. The first element becomes the last one.
  • rb : rotate b - shift up all elements of stack b by 1. The first element becomes the last one.
  • rr : ra and rb at the same time.
  • rra : reverse rotate a - shift down all elements of stack a by 1. The last element becomes the first one.
  • rrb : reverse rotate b - shift down all elements of stack b by 1. The last element becomes the first one.
  • rrr : rra and rrb at the same time.

Installation

git clone https://github.com/a-parfenov/Push_swap.git && cd push_swap && make

Run

Launch the visualizer, submit 100 numbers:

python3 pyviz.py `ruby -e "puts (1..100).to_a.shuffle.join(' ')"`

Starting the sorting algorithm (displays only the commands used):

./push_swap 3 0 2 1 4

Launching the sorting algorithm and checker (displays the result of the work):

ARG="5 3 6 0 2 1 4"; ./push_swap $ARG | ./checker $ARG
ARG=`ruby -e "puts (1..100).to_a.shuffle.join(' ')"`; ./push_swap $ARG | ./checker $ARG

Visualization

pushswap