Algorithm overview - jgrigorjeva/push_swap GitHub Wiki

The algorithms

There are quite a few algorithms to consider for the push_swap project:

1. Brute force: Generate all possible combinations of operations and test which one sorts the stack.

+ the solution is always optimal

- not great for larger input

2. Greedy Algorithm Push the smallest element from stack A to stack B. In the end, the stack B is ordered from largest to smallest number, so the last step would be to push all elements (one by one) back to A.

+ simpler to implement and faster than brute force

- may not meet the benchmark number of operations

3. Divide and Conquer This one is interesting. First you create a sorted copy of the stack A and divide it into chunks (the chunk size may depend on the input size, usually between 5 and 20 members). For example, if A contains elements [1, 2, ..., 100], divide it into:

Chunk 1: [1, 20]
Chunk 2: [21, 40]
Chunk 3: [41, 60]
etc.

Then you push elements from the unsorted stack A to stack B, but only those belonging to chunk 1. Use allowed operations (sa, ra, rra) to move the closest* element from the chunk 1 to the top of A, then push it to B. When pushing to B, sort B by moving smaller elements to the bottom. Repeat for all chunks, push sorted B back to A. By dividing A into chunks, you decrease the number of operations needed to sort B compared to the Greedy Algorithm.

* Closest would mean: needing the least amount of operations to be moved to the top of A

4. Insertion Sort Simulation Push elements from A to B while keeping B sorted. Push elements back to A in sorted order.

- Can be inefficient for large inputs so I didn't go into much detail

5. Turk algorithm The algorithm of my choice. More details will be provided on the following page.

+ Consistently gives good results that meet the benchmark

- Requires more background calculations than radix sort and is not so easy to implement

5. Radix Sort Order numbers based on their digits starting from the least significant digit. In this case, we use the binary representation of the element, so first, the numbers are grouped together based on their least significant bit, then next bit up to the most significant bit. Originally, I chose this algorithm, so I will go into more details on the next page.

+ easy to implement and efficient for large inputs - not good enough to get 100 % in eval, even after some optimizations

6. Optimal Sorting Algorithms This approach combines different algorithms that are applied based on the input. E.g. for small inputs (n <= 5) use brute force predefined solutions, for medium inputs n <= 100) use Divide and conquer, for large inputs n <= 500) use radix sort.

+ efficient solutions for all input sizes

- more code