You have to sort numbers in stack (stack a) of integers in ascending order using only two stacks a and b (b is empty).
Using eleven operations: sa : swap a - swap the first 2 elements at the top of stack a sb : swap b - swap the first 2 elements at the top of stack b. ss : sa and sb at the same time. pa : push a - take the first element at the top of b and put it at the top of a. pb : push b - take the first element at the top of a and put it at the top of b. ra : rotate a - shift up all elements of stack a by 1. The first element becomes the last one. rb : rotate b - shift up all elements of stack b by 1. The first element becomes the last one. rr : ra and rb at the same time. rra : reverse rotate a - shift down all elements of stack a by 1. The last element becomes the first one. rrb : reverse rotate b - shift down all elements of stack b by 1. The last element becomes the first one. rrr : rra and rrb at the same time.
What is the fastest Algorithm that you can use that takes advantage of all these operations?
The first one is the shortest, shortest sorting algorithm. It is described by Simon Huygens in a paper he wrote back in 1984 called 'A Simple Algorithm Against Sparse Algorithms', but it has become a lot more popular since then thanks to the fact that it is based on a very complex algorithm called Fletch-Fuzzy. To make a good approximation of this algorithm, a function called f, a pair of integers is given using the formula
f(a) = (a+1) / f(a)
that shows that
(a) = f(a) / f(x)
and
(x) = f(a) / f(x)
There were no other ways to solve such a calculation than by using complex algorithms, such as solving for the least important factor of z. Here is my implementation.
Example 6 A simple algorithm that takes advantage of some complex algorithms.
I find this article helpful. A simple algorithm that is better than a recursive recursive algorithm. The result of all the recursive ones is the longest sorting algorithm ever invented and not based on any hard number.
Nathan Bell
Pop them one-by-one into an array. O(n) time. Use a normal O(n log n) sorting algorithm like mergesort. Push them back into the stack. O(n) time.
O(n log n) time overall.
Problem?
Aaron Roberts
Since when are there actual bots on Any Forums?
Austin Jackson
since GPT-Any Forums dropped
Hudson Rogers
/thread Otherwise you'd have to implement the operations on the stack itself, I.E.: on the linked list (usually). Which automatically pushes the runtime up to: O(n2logn)
Iterate until the original stack is empty and in each iteration, pop an element from the original stack, while the top element in the second stack is bigger than the removed element, pop the second stack and push it to the original stack. Now you can push the element you originally popped off the original stack to the second stack.
The time complexity of this approach is O(N^2).
Nicholas Kelly
Having trouble with push swap user?
Noah Taylor
I just don't want to reinvent the wheel fellow 42 user
Elijah Evans
Just search for "radix sort push swap" and you'll find a medium article a chinese dude wrote on it, that's the easiest way I found to complete the project. The actual sorting code is there in C++ but it's pretty simple, you can easily convert it to C. It's not gonna get you full points, but it'll pass easy peasy.
You do need to find a way to order the numbers to a list such as {0,1,2,...,N}, being N - 1 the number of args you're giving it, but keeping the order. If you're passing the program {-12, 34, 12, 4}, the list needs to be {0, 3, 2, 1}.
Read the article and understand how the algorithm works. Then go read about bitwise and bitshift operators, as that's how the algo sorts, it compares the numbers in binary and orders them that way.
You'll need a different algorithm for sorting if there are only 3/4/5 numbers, but that's the easy part.
I ended up using arrays, but linked lists work as well. Make sure your operation functions such as sa or pa are working properly and work in all edge cases, as that could fuck you up.
I'll check back the thread in a couple of hours if you need more help. Who would've thought you'd be getting decent help here . Try searching slack as well for posts containing "push_swap", there's usually interesting info there.
Jaxson Lewis
This looks like homework. Do it yourself, user!
Brayden Howard
just to add to this, this is a qucik and dirty way to pass the project. There's still work involved in coding everything, getting the stacks ready for the algo, coding the operations, etc, but you're missing out on learning a bit more about algorithms.
With that said, no judging if you take the easy way out.
Christopher Collins
Yes
Robert Parker
No, it’s impossible. Look up Tower of Hanoi problem.
Carter Evans
Wait you get full points only if your algorithm is the best?
Logan Powell
>copy to array >sort >copy back to stack
Jace Baker
What project are you talking about?
Anthony Martinez
It's a 42 school project, push_swap, google it.
read the subject bro, cmon
Dominic Taylor
What the fuck kind of bullshit stack implementation is this This is like the CS version of Houdini chain escape
