This project has been created as part of the 42 curriculum by

📚 Description

The Push Swap project is a simple, yet highly structured, algorithmic challenge: you must sort a list of elements using a limited set of instructions.

You are given a set of integer values, two stacks (A and B), and a set of instructions to manipulate both stacks. Your task is to write a C program called push_swap that calculates and displays the shortest sequence of instructions needed to sort the given integers in Stack A.

⚙️ Instructions

To test the program, you first need to compile the source files and then run the executable with your test cases.

The build process is automated by Make. Running make will build the executable program:

You can then run the program with a list of space-separated integers:

./push_swap 12 345 54 32 11 1

🔗 Resources

For excellent resources on various Push Swap algorithms, I recommend checking out these articles:

• Turk's Algorithm
• Chunk Sort
• Radix Sort

🤖 AI Usage

The AI was helpful in suggesting good external articles and concepts. However, for assistance with the project implementation itself, its utility are limited. Therefore, the best use of AI is to find external resources rather than relying on it as the sole source for the solution.

💡 Implementation Journey

Initially, my goal was to find and use the single "best" algorithm. However, I quickly realized that there isn't one—success is about continuous trying, testing, and refinement.

1. First Attempt: Radix Sort I decided to start with the Radix Sort algorithm because it utilizes bitwise operations, offering a valuable opportunity to expand my knowledge of bit manipulation. After implementing the basic logic, I encountered the issue of handling negative values, which would have required significant additional work.

2. Second Attempt: Turk's Algorithm At this point, I decided to switch and try Turk's Algorithm. After a week of implementation, I achieved respectable results, typically under 700 moves for small inputs and under 5500 moves for larger sets. The main issue was a lack of consistency; certain worst-case scenarios caused the move count to exceed the required limits. Despite spending more days on optimization, the results remained inconsistent.

3. Third Attempt: Chunk Sort I then moved on to Chunk Sort, having heard about its good results. After two days, it also delivered good move counts, but like Turk's, it wasn't perfectly consistent. While it resulted in less and more readable code, I ultimately decided to revert to Turk's Algorithm, as I had spent more time on it and felt I understood its mechanics better.

Approach Details (Turk's Algorithm)

1. Initial Processing

• Parsing and Validation: I first parse the input arguments, checking for invalid numbers, duplicate elements, values exceeding the integer limit, and ensuring correct handling of single-string inputs.
• Pre-sort Check: I check if the arguments are already sorted. If they are, the project specification requires no action.
• Memory Management: A simple Garbage Collector was implemented. After each successful memory allocation (malloc), the address is registered in a linked list. This list is freed entirely upon program exit or any earlier failure, preventing memory leaks.

2. Stack Setup

• Assuming the input is not already sorted, all arguments are pushed into a linked list representing Stack A.

3. Sorting Small Inputs

• The size of the input is checked. Small inputs (like 2, 3, or 5 elements) are handled with a specific, hardcoded logic. This approach guarantees an efficient and minimal number of actions in the worst-case scenario.

4. Core Algorithm (Input Size > 5)

If the input size is greater than 5, the tuck function is called.

Phase 1: Pushing Elements from A to B (Keeping B Sorted Descending)

1. Initial Push: The first two nodes are pushed from Stack A to Stack B to serve as a basic structure.
2. Best Position/Cost Calculation: The core of the algorithm involves pushing each subsequent node from Stack A to the best position in Stack B.
   • The "best position" means finding the target element in B: the largest element in B that is still smaller than the element we want to push from A. Pushing it on top of this target maintains a descending order in B.
   • For every element in A, the total cost to move it to the top of A and move its target to the top of B is calculated.
   • The element with the cheapest total cost is selected.
3. Execution: The moves corresponding to the cheapest cost are executed, and the winning element is pushed from A to B (pb).
4. Repeat: This process is repeated until only three nodes remain in Stack A. These final three nodes are sorted using the basic sort_3 algorithm.

Phase 2: Pushing Elements Back from B to A (Achieving A Sorted Ascending)

1. Reverse Target: Elements are moved back from B to A. The goal now is to find the smallest element in A that is still larger than the element we want to push from B.
2. Cost and Selection: The cost to bring the target element to the top of A is calculated, and the cheapest direction is chosen.
3. Execution: The moves are executed, and the element is pushed from B to A (pa), building an ascending order in A.
4. Repeat: This continues until Stack B is empty.

Phase 3: Final Alignment

1. After all elements are back in A, the stack is sorted circularly (the smallest element is somewhere in the middle).
2. The final step is to find the smallest element in A and bring it to the top using the minimum number of rotations, thus achieving the fully sorted, ascending result.