Push_swap

This project involves sorting data on a stack, with a limited set of instructions, and the smallest number of moves. To make this happen, you will have to manipulate various sorting algorithms and choose the most appropriate solution(s) for optimized data sorting.

What is Push_swap?

Push_swap is an individual project at 42 that requires us to create a program that sorts a stack(a) using an auxiliary stack(b) using specific commands: sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb and rrr. The challenge is to implement an algorithm that sorts with the least amount of operations possible, for example an entry of 100 numbers should not exceed 700 operations to reach the maximum score and for 500 random numbers the maximum is 5500 operations. As a bonus we must create a program that validates if the operations that the main program (push_swap) printed, orders stack(a) and checks if stack(b) remains empty at the end. The algorithm used to order more than 10 arguments is a combination of selection sort and the idea of divide and conquer.

*Check the operations table for a complete description of each operation or the mini game by phemsi-a.

Overview (push_swap_gui)

Click here to access the push_swap_gui repository .

Badge

Objectives

• Sorting algorithms
• Battery concept and handling elements
• Algorithm implementation

Skills

• Imperative programming
• Unix
• Rigor
• Algorithms & AI

My grade

Getting started

Follow the steps below

# Clone the project and access the folder
git clone https://github.com/wwwwelton/push_swap && cd push_swap/

# Compile push_swap and checker with
make && make bonus

# Running push_swap
./push_swap 1 3 2 5 4

# Will output
ra
pb
pb
ra
pb
ra
pa
rrb
pa
pa
rra

# Running checker
./checker 1 3 2 5 4

# Type each operation followed by enter
# and at the end press control + D to finish reading commands
ra
pb
pb
ra
pb
ra
pa
rrb
pa
pa
rra

# Will output
OK

# Running push_swap with the checker (doesn't work on zsh)
ARG="1 3 2 5 4"; ./push_swap $ARG | ./checker $ARG

# Running push_swap with the checker (works on zsh)
./push_swap 1 3 2 5 4 | ./checker 1 3 2 5 4

# Will output
OK

# Installing push_swap_gui (graphical command interpreter)
pip3 install push_swap_gui

# Running push_swap_gui
python3 -m push_swap_gui

# Uncheck the box "use built-in algo and click on "choose file..."
# Select push_swap compiled binary

# Click on "Generate new (a, b)" followed by "Calculate"
# and finally click on play button

# Will output

# Use the arrows to reduce or increase speed
# Enjoy =D

# Clean output files with
make fclean

# Well done!

Game rules

• The game is composed of 2 stacks named a and b.
• To start with: a contains a random number of either positive or negative numbers without any duplicates. b is empty
• The goal is to sort in ascending order numbers into stack a.
• To do this you have the following operations at your disposal:

Operations
op	description
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.

Updating

The project is regularly updated with bug fixes and code optimization.

📝 License

This project is licensed under the GNU General Public License v3.0 - see the LICENSE file for details.

---

Made by Welton Leite 👋 See my linkedin