Skip to content

Latest commit

 

History

History
80 lines (53 loc) · 2.44 KB

README.md

File metadata and controls

80 lines (53 loc) · 2.44 KB
Raw

🧠 push_swap

About

push_swap is a C project that implements an efficient sorting algorithm to sort a stack of integers using a limited set of operations. The challenge is to sort the stack with the minimum number of moves, demonstrating the importance of algorithm optimization and stack manipulation.

💻 Installation

To compile and test push_swap, follow these steps:

  1. Clone the repository:

    git clone git@github.com:AnnLvu/push_swap_42.git
cd push_swap_42

  2. Compile the project:

    make

  3. Run the simulation:

    ./push_swap <list_of_integers>

🚀 Usage

You can use the program with the following commands:

Sort the stack:

./push_swap <list_of_integers>

Check if the stack is sorted:

./push_swap <list_of_integers> | ./checker <list_of_integers>

🧠 How It Works

Available Operations

The program sorts the stack by using the following operations:

  • sa: Swap the top two elements of stack A.
  • sb: Swap the top two elements of stack B.
  • ss: Swap both stack A and stack B.
  • pa: Push the top element of stack B onto stack A.
  • pb: Push the top element of stack A onto stack B.
  • ra: Rotate stack A (shift all elements up by 1).
  • rb: Rotate stack B (shift all elements up by 1).
  • rr: Rotate both stack A and stack B.
  • rra: Reverse rotate stack A (shift all elements down by 1).
  • rrb: Reverse rotate stack B (shift all elements down by 1).
  • rrr: Reverse rotate both stack A and stack B.

Sorting Algorithm

The push_swap algorithm carefully selects the most efficient operations to minimize the total number of moves required to sort the stack. It handles stacks of various sizes and complexities, from small stacks to larger, more challenging ones.

⚠️ Known Issues

  • Performance on large inputs: While the algorithm is optimized for various input sizes, very large stacks may still require additional performance tuning.
  • Edge cases: Some edge cases, such as duplicates or invalid inputs, are not explicitly handled and should be avoided.

🎯 Conclusion

The push_swap project is an exercise in algorithm optimization and efficient stack manipulation. It demonstrates the importance of choosing the right operations to minimize computational complexity and is an excellent example of using data structures to solve real-world problems.