(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:
| Command | Description |
|---|---|
| sa | Swap the first two elements at the top of stack a |
| sb | Swap the first two elements at the top of stack b |
| ss | Swap the first two elements at the top of both stacks |
| pa | Take the first element at the top of b and put it at the top of a |
| pb | Take the first element at the top of a and put it at the top of b |
| ra | Shift up all elements of stack a by 1. The first becomes the last |
| rb | Shift up all elements of stack b by 1. The first becomes the last |
| rr | Shift up all elements of both stacks by 1. The first becomes the last |
| rra | Shift down all elements of stack a by 1. The last becomes the first |
| rrb | Shift down all elements of stack b by 1. The last becomes the first |
| rrr | Shift down all elements of both stacks by 1. The last becomes the first |
Allowed external functions:
- read, write, malloc, free, exit
- Clone the repo
- 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.- 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
- 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.
- 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
| Inputs | Operations |
|---|---|
| 3 | 1.49 |
| 5 | 8.91 |
| 10 | 34.27 |
| 25 | 100.79 |
| 50 | 238.85 |
| 100 | 578.47 |
| 200 | 1463.09 |
| 300 | 2521.83 |
| 400 | 3742.26 |
| 500 | 5096.81 |
| 1000 | 13500.86 |
Made by Frederick Schubert: fschuber@student.42heilbronn.de | http://frederickschubert.de