Push_swap

Push_swap

This will just be a thought collection or code snippet storage. Not a detailed walkthrough or example of push_swap.

This project involves sorting a stack of integers in the least amount of operations possible.

Algorithm

I start by pushing all the elements but 3 from stack a to stack b. Or if stack a is already sorted while pushing to stack b I stop pushing prematurely. After pushing everything into stack b I start sorting them back to stack a.

For every push finding the least amount of operations for the current status of both stacks. There are 4 sort types to check;

• both stacks rotate
• both stacks reverse_rotate
• stack a rotate, stack b reverse_rotate
• stack a reverse_rotate, stack b rotate

Then sort according to the most optimal of these 4 options. Repeat this sorting process until the entire stack is sorted.

Small sort

There are some extra requirements for sorting low n size stacks.
The sorting of stack size 5 should be a maximum of 12 operations.
The sorting of stack size 3 should be a maximum of 3 operations.

Sort 3

If the order of the integers is stacked in the following order the maximum amount of operations will be a maximum of 2.

• if 012 -> sorted //do noting when this is the case
• if 102 -> swap //now is sorted
• 210 -> swap //new state = 120
• 021 -> swap //new state = 201
• 120 -> sorted after 1 rev_rot //now is sorted
• 201 -> sorted after 1 rot //now is sorted

Sort 5

When using the Sort 3 combined with the normal algorithm the amount of operations will be lower than the 12 operation limit.

Useful link dump

Online-visualizer

Random number input generator