(because swap_push just isn't as natural.)

This project was created in compliance with the 42 norm, which means no ternary operators, no switches, no for loops, no in function comments, ... -> https://github.com/FreddyMSchubert/42_cursus/blob/main/en.norm.pdf

[2] [ ]
[1] [ ]
[3] [ ]
[6] [ ]
[5] [ ]
[8] [ ]
 a -- b

Given 2 stacks a and b where b is emtpy and a is filled with a random amount of non-duplicated signed integers, sort numbers in ascending order into stack a with the following operations:

Allowed external functions:

• read, write, malloc, free, exit

1. Clone the repo
2. To run it, you can do the following:

./push_swap 3 1 5 8 2 7		// runs the executable
./run_push_swap.sh 25		// runs the executable with 25 random inputs
./get_average.sh 100 30		// runs the executable with 30 random inputs
							// 100 times and prints average, lowest and highest values
./finetuning.sh 1 50 100	// gets the average from 100 executions with random inputs
							// for all values between 1 and 50.

3. In the header file, the VERBOSE macro can have the following values:
   • 0 -> normal, subject specified program output
   • 1 -> detailed logging
   • -1 -> outputs 0 output + the amount of operations. useful for e.g. get_average script

1. The operation efficiency matters, and while the program should be relatively performant, there's absolutely no problem e.g. creating a sorted stack as the very first thing to simplify things like finding a median.
2. One algorithm alone is not going to cut it.

I started out implementing a bunch of algorithms and seeing how efficient they would turn out to be. Here's what I made:

To be clear, these are all pretty different to their usual implementations. I just called the algorithms what they most closely resembled.

Insertion Sort: First, push all elements into stack b. Then, continue rotating b to the highest element possible and pushing it back to stack a until the stack is sorted.
Why is it not included: We lose a lot of moves where we do no sorting at all by pushing things to b. If we can find a way to sort the elements a little while pushing to b and then ensure correct order when pushing back, we'd be much better off. (-> K Sort)

Quick Sort: Recursively, pick a pivot, push everything above the pivot to the other stack, and call yourself on both halves. When you get called and your selected area is below a threshhold, apply bubble sort instead of setting another pivot.
Why is it not included: This would have been the most complicated algorithm, and I didn't get it done before coming into contact with K sort, which blew it out of the water in terms of efficiency.

Bubble Sort (< 5 stack-len): If the current value is larger than the next, swap them, otherwise rotate the stack.
Problem: Since the stacks wrap around, you will go in an infinite loop.
Solution: Just don't swap the elements if the element at index 0 is the one that will end up being at the very end of the sorted stack.

Cheap Quick Sort (< 10 stack-len): Quick sort, but it's not recursive. You just set a pivot once and apply bubble on both halves.
Why have it at all: Because surprisingly, it actually surpasses both bubble and k sort in operation efficiency for some low-range values.

K Sort (> 9 stack-len): Insertion sort, but with some sorting while pushing values over to b. This pre-sorting only occurs within a certain stack-len relative range though. This creates a K-like shape in b and can be pushed back to a while finishing the sorting very efficiently.

These values are averages over many program calls with random numbers. Test the performance yourself with the /build/get_average.sh script.

click on the image to get an interactive graph

Made by Frederick Schubert: [email protected] | http:https://frederickschubert.de