Skip to content

My solution for the push_swap project of 42 school.

Notifications You must be signed in to change notification settings

tblaase/push_swap

Repository files navigation

push_swap 86/100

This is my solution for the push_swap project of 42 school.


This code is capable of

  • handeling inputs that look like "2 1 3 4 5" or 2 1 3 4 5 or 2 1 "3 4 5"
  • detecting a non-numeric, greater or smaller than integer or double number input
  • sorting 3 random integers in 1 or 2 actions
  • sorting 5 random integers in 5 to 10 actions
  • sorintg 100 random integers with an average of ca. 757 actions
  • sorting 500 random integers with an average of ca. 7248 actions
    (both average amount of actions where the average of 1000 random tests)

This code is not capable of

  • sorting 6-45 random integers with a 100% success rate
    (with 45 random integers the success-rate is 99.9% when testing 1000 different cases)

explanation of my algorithm

100 number sort(ft_big_sort)

For 100 Numbers i split my stack into 4 parts.

  • Step 1: Find the corresponding borders to split my stack into 4 parts, equal in size.
  • Step 2: push the first quarter to stack B
  • Step 3: search for the biggest and the smallest number in stack B
  • Step 4: rotate the biggest number to the top of stack B and push it to stack A
  • Step 5: rotate the smallest number to the top of stack B, push it to stack A and rotate it to the bottom
  • Step 6: repeat steps 4 and 5 until stack B is empty
  • Step 7: rotate all my sorted numbers from the top of stack A to the bottom of stack A
  • Step 8: repeat steps 2 to 7 for the remaining quarters
  • Step 9: have your numbers sorted by ascending order in stack A, with the smallest number on top of your Stack

500 number sort(ft_big_big_sort)

This works very similar to the 100 number sort, but instead of splitting my stack into quarters i split it into eighths.

how to use the algorithm

This will compile my code into an executable called push_swap and delete all unnecesarry files that were created during compilation.

make call

To use the visualizer i used in the example below.
This visualizer is not mine, you can find it here.

python3 pyviz.py `ruby -e "puts (1..50).to_a.shuffle.join(' ')"`

visualization of my algorithm sorting 50 random integers


Releases

No releases published

Packages

No packages published