push_swap

This project involves sorting data on a stack, with a limited set of instructions, and the smallest number of moves.

_{(In those pictures, I am using this visualizer)}

Description

_{(subject is included in the root of the repo)}

The Push swap project is a very simple and a highly straightforward algorithm project:
data must be sorted.

Writing a sorting algorithm is always a very important step in a developer’s journey. It is often the first encounter with the concept of complexity.

The learning objectives of this project are rigor, use of C, and use of basic algorithms.
Especially focusing on their complexity.

Sorting values is simple. To sort them the fastest way possible is less simple. Especially because from one integers configuration to another, the most efficient sorting solution can differ.

The Rules

• There are 2 stacks named a and b
• At the beginning:
  • The stack a contains a random amoutnt of negative and/or positive numbers which cannot be duplicated.
  • The stack b is empty.
• The goal is to sort in ascending order numbers into stack a. To do so you have the following operations at your disposal:
  • 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.

Install and Run

_{(tested on Ubuntu)}

git clone https://github.com/VulpesDev/push_swap.git ~/push_swap_Vulpes && cd ~/push_swap_Vulpes && make && echo && echo && ./push_swap 1 -31 23 -102 42

To Install the tester

cd ~/push_swap_Vulpes && make bonus

Usage

Just run the executable "./push_swap" with the numbers of stack a as arguments_{(numeric values only; no repeating values; int max and int min are limits;)}
Then it will print out the instructions which sort the stack.

./push_swap -1 -42 -1111 5421 2 -1112 241 2414 62331 2124

If you also compile the tester, you can pipe the output to the tester and check if stack a is sorted.

./push_swap 24 -24 52 134 5123 0 | ./checker 24 -24 52 134 5123 0

Pro Tip

You can use this visualizer to see how my algorithm works!