• Explanation of the "push swap" algorithm
  • Project Implementation
    • 1. Parsing of Arguments
    • 2. Overflow Check
    • 3. Elimination of Duplicates
    • 4. Conversion of Numbers by Position
    • 5. Update of Stack A and B Information
    • 6. Sorting Algorithm for Three Elements
    • 7. Algorithm for Sorting Five or Four Elements
    • 8. Algorithm for Sorting Any Number of Values (N)
    • 9. Optimization of Movements
    • 10. Finalization
• Running the Push Swap Program
  • Prerequisites
  • Building the Program
  • Using the Program
  • Counting the Number of Instructions
  • Checking the Sorting
  • Platform Compatibility
• Thank you

The "push swap" algorithm is used to sort an array of integers using two stacks, which we'll refer to as A and B. The possible moves are as follows:

At the beginning of the "push swap" project, you followed these steps:

1. Parsing of Arguments: You parsed the arguments passed to the program to ensure that they are all numbers, allowing for "-" and "+" signs for negative and positive numbers.

2. Overflow Check: You implemented a conversion technique to determine if values exceeded the limits of an integer (INT_MAX and INT_MIN). You used two converters, one for integers and another for longs, and if the two conversions differed, it indicated overflow.

3. Elimination of Duplicates: Once the array was created, you iterated through the array to ensure that there were no duplicates using a nested loop.

4. Conversion of Numbers by Position: To simplify the algorithm, you assigned each number a value based on its position in the array, so as to avoid large gaps between numbers.

5. Update of Stack A and B Information: You calculated and updated information such as size, median, maximum, and minimum for stacks A and B.

6. Sorting Algorithm for Three Elements: You implemented an algorithm that found the minimum and maximum in stack A, then placed them in the correct order using movements.

7. Algorithm for Sorting Five or Four Elements: You used a pivot algorithm to send the minimum elements from stack A to stack B. This process was repeated until three elements remained in stack A, at which point you applied the three-element sorting algorithm.

8. Algorithm for Sorting Any Number of Values (N): You utilized a pivot algorithm based on the median. If an element was the median, it was "pushed" to stack B. This process was repeated until three elements remained in stack A, at which point you applied the three-element sorting algorithm.

9. Optimization of Movements: You sought to minimize the number of movements by using a cost calculation to decide on optimal moves.

10. Finalization: You determined if ra or rra movements were more efficient for arranging the remaining elements in order before completing the sorting.

Before running your "push swap" program, make sure you have the following prerequisites:

• A Linux operating system.

To build your "push swap" program, you can use the make command. Ensure that you have a Makefile set up for your project. Here's how you can build it:

make

This command will compile your program and generate an executable called push_swap.

You can execute your "push swap" program by providing a series of integer arguments. You can run it using the following command:

./push_swap $ARGS

Replace $ARGS with the list of integers you want to sort. The program will output a series of instructions for sorting the input.

If you want to count the number of instructions generated by your "push swap" program, you can use the wc -l command as follows:

./push_swap $ARGS | wc -l

This will display the total count of instructions.

Before you need to create the checker program, you need to do:

make bonus

or

make checker

To verify the correctness of the sorting instructions, you can use the checker program. Execute the following command:

$ARGS="3 5 1 2 4"; ./push_swap $ARGS | ./checker $ARGS

If the input was sorted correctly, the checker program will output "OK." Otherwise, it will display "KO."

Or you can run the script, it's located in the script folder. You need to be at the root of the project and type the following command:

./script/tester.sh

Please note that your "push swap" program is designed to work on Linux-based operating systems. It may not function on other platforms due to platform-specific system calls and dependencies.

Make sure you are running the program on a Linux system for it to work as intended.

Enjoy using your "push swap" program to efficiently sort integers!

Finally, thanks to tools available on GitHub, such as submodules for testing and visualization, you were able to develop and refine your implementation of the "push swap" algorithm.