Skip to content

Latest commit

 

History

History
137 lines (110 loc) · 4.78 KB

README.md

File metadata and controls

137 lines (110 loc) · 4.78 KB
Raw

Push_Swap

push_swap_badge/

In this repository, you can accsess the code created for the Push Swap project, mandatory and bonus part.

Final score

push_swap_grade/
Keywords Skills
- Sorting algorithms - Rigor
- Battery concept and handling elements - Unix
- Algorithm implementation - Algorithms & AI
- Imperative programming

Visual implementation of my algorithm:

algorithm_gif/

About

This project involves creating a program to sort a list of numbers in ascending order using a set of predefined movements. The sorting process utilizes two stacks, Stack A and Stack B:

  • Stack A: Initially holds the list of numbers that need to be sorted.
  • Stack B: Starts empty and is used as an auxiliary stack during the sorting process.

The objective is to transfer the numbers from Stack A to Stack B using the defined operations to achieve a sorted sequence in ascending order.

The challenge lies in performing this sorting efficiently while adhering to the constraints and movement rules provided.

Turk Algorithm

The success of this project hinges on the Turk Algorithm, which was developed by Ali Ogun, another 42 student. You can find a detailed explanation of the algorithm in his article, "Push Swap — A journey to find most efficient sorting algorithm". I highly recommend reading this article to gain a deeper understanding of how the algorithm works.

Allowed Operations:

Movement How it works
pa Take the first element at the top of B and put it at the top of A. Do nothing if B is empty.
pb Take the first element at the top of A and put it at the top of B. Do nothing if A is empty.
sa Swap the first 2 elements at the top of stack A. Do nothing if there is only one or no elements.
sb 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.
ra Shift up all elements of stack A by 1. The first element becomes the last one.
rb 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 Shift down all elements of stack A by 1. The last element becomes the first one.
rrb Shift down all elements of stack B by 1. The last element becomes the first one.
rrr rra and rrb at the same time.

Run it with:

  $> ./push_swap <random_numbers>

It must display the list of instructions used to sort the list of numbers.

Bonus ⭐

Consists in writing a checker program that verifies whether an unsorted list can be sorted using a given list of move instructions.

Run it with:

  $> ./checker <random_numbers>

You will need to input a list of move instructions for the program to execute and sort the numbers. Each instruction should be on a new line. To complete your input, press "Ctrl+D".

  • If the instructions successfully sort the numbers, the program will display "OK".
  • If the instructions do not sort the numbers correctly, it will display "KO".
  • If you enter an invalid instruction or an incorrect list of numbers, the program will display "Error".

    • Usage

    Clone this repository in you local computer using a terminal: 

    $> git clone [email protected]:AnaVolkmann/42_PUSH_SWAP.git

    After cloning the project to your local repository, you can use the following commands from the Makefile:

    • make all: or just make compiles the project
    • make clean: deletes the object files created during compilation
    • make fclean: executes the clean command and also deletes the binary files
    • make re: runs the fclean command followed by make all to recompile the project
    • make bonus: compiles the project with bonus features (if applicable)
    • make rebonus: runs the fclean command followed by make bonus to recompile with bonus features